Превратить мультикарту в набор множеств - PullRequest
Новая
       22

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

5 голосов
/ 09 ноября 2010

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

Ответы [ 4 ]

2 голосов
/ 09 ноября 2010

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

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

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

1 голос
/ 09 ноября 2010

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

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

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

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

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

спары value_type.

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

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

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

1 голос
/ 09 ноября 2010

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

1 голос
/ 09 ноября 2010

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

Сначала вы определите пару.Для пары необходим ключ в качестве первого элемента, а ваш экземпляр - во втором.

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

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-битных приложений вам придется изменить это!).Я должен признать, что это не самый лучший трюк.

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

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

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

...