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

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

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

Или что-то вроде того.

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

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

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

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

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

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

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

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

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

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

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

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

с парами value_type.

В любом случае, operator[] для external_set создаст пустой внутренний набор, если iter->first не найден, и извлечет существующий, если ключ уже существует.

Это будет работать, но не будет самым эффективным способом сделать это. Причина в том, что мы знаем, что 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::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 );
}

У этого по-прежнему есть преимущество в том, что нам не нужно искать, когда мы нажимаем повторяющуюся клавишу, но есть недостаток, заключающийся в том, что мы не можем передать «подсказку» оператору [], как мы могли бы вставить.