将多重贴图转换为一组集合

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

现在您可以使用 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，则可以将同一本书添加两次，这可能是不需要的。

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 对。

无论哪种方式，如果未找到 iter->first，outer_set 上的operator[]将创建一个空的内部集，如果键已经存在，则将检索现有的内部集。

这会起作用，但不是最有效的方法。原因是我们知道 p.first 要么匹配我们看到的最后一个键，要么我们必须在末尾插入，但上面每次都进行查找。因此，更有效的方法是保留我们的集合迭代器。这里的 value_type 是我们的 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 );
}

请注意，我们在插入时捕获迭代器，它是 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 );
}

这仍然具有当我们按下重复键时不必查找的优点，但缺点是我们无法像插入一样将“提示”传递给operator[]。