Превратите мультикарту в набор наборов

Question

У меня есть мультикарта, и я хотел бы получить набор наборов, которые группировали бы все элементы типа A в мультикарте, имеющие один и тот же ключ.Есть ли встроенный способ сделать это в STL?

Answer 1

Я не думаю, что есть встроенный способ. Однако это легко сделать вручную:

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

Или что-то типа того.

Answer 2

Вы можете использовать набор на пару.

Сначала вы определяете пару.Паре нужен ключ в качестве первого элемента и ваш экземпляр в качестве второго элемента.

Например.Предположим, у нас есть коллекция книг, и мы хотим сгруппировать их по авторам:

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

Затем вы определяете набор для этой пары:

typedef set<AuthorBookPair> BooksGroupedByAuthor;

Заполнение набора можно сделать так:

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

Теперь вы можете просто искать книги автора, используя методы low_bound и 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));

Теперь просто перебирайте нижнюю и верхнюю границы, чтобы получить все книги этого автора.

Этот трюк основан на том факте, что я решил хранить указатели на книги и знаю, что такое самый маленький и самый большой указатель (для 64-битных приложений вам придется это изменить!).Надо признать, это не самый красивый трюк.

Немного лучшей альтернативой было бы хранить сами книги (если в вашем приложении разрешено делать копии этих экземпляров) и создавать два конкретных экземпляра Book, которые представляют собой «самую маленькую книгу» и «самую большую книгу» соответственно.

Плюс этого трюка в том, что он позволяет при необходимости добавить больше измерений.Например.вы можете добавить год в качестве второго измерения, а затем выбрать поиск книг только автора или поиск книг автора определенного года.При использовании большего количества измерений могут пригодиться кортежи из нового C++0x.

Преимущество этого трюка еще и в том, что он защищает вас от повторного добавления книги.Если книга добавлена ​​дважды, она все равно окажется в коллекции один раз (если предположить, что автор книги никогда не меняется).Если бы вы использовали multi_map, вы могли бы добавить одну и ту же книгу дважды, что, вероятно, нежелательно.

Answer 3

Вы можете сделать что -то вроде (но с более подходящими именами) следующим образом. Обратите внимание, что выходная структура на самом деле является картой наборов, а не набором набора, потому что таким образом вы сохраняете ключи.

#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

Это создает карту наборов. Набор наборов на самом деле не имеет смысла.

Для каждого элемента в вашем наборе вы можете сделать:

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

Если у вас есть итераторы или

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

с парами value_type.

В любом случае, Operator [] on outter_set создаст пустой внутренний набор, если ITER-> сначала не найден, и получит существующий, если ключ уже существует.

Это будет работать, но не будет наиболее эффективным способом сделать это. Причина в том, что мы знаем, что P.First либо соответствует последнему ключу, который мы видели, либо мы должны вставить в конце, но приведенное выше каждый раз делает поиск. Таким образом, более эффективным способом является удержание нашего итератора. value_type Вот тип значения нашего мультимапа

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

Обратите внимание, что мы захватываем итератор во время вставки, это первая из пары, возвращенной STD :: Map.

Если вы не хотите работать с итераторами, вы можете использовать указатель на STD :: Так.

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

Это все еще имеет преимущество в том, что не нужно смотреть вверх, когда мы достигли дублированного ключа, но имеет недостаток, что мы не можем передать «намек» оператору [], как мы могли вставить.