5

我有一个多重映射，我想获得一组集合 - 它将多重映射中共享相同键的所有 A 类型的项目组合在一起。在 STL 中是否有内置方法可以做到这一点？

4

4 回答 4

2

我认为没有内置的方法。但是手动操作很容易：

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

或类似的东西。

于 2010-11-09T11:07:30.023 回答
1

您可以在一对上使用一组。

首先，您定义该对。该对需要密钥作为第一个元素，您的实例作为第二个元素。

例如，假设我们有一系列书籍，我们想按作者对它们进行分组：

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

现在只需在lowerbound 和upperbound 之间进行迭代以获取该作者的所有书籍。

这个技巧依赖于我选择存储指向书籍的指针这一事实，并且我知道最小和最大指针是什么（对于 64 位应用程序，您必须更改它！）。我必须承认这不是最好的把戏。

更好的选择是存储书籍本身（如果您的应用程序允许复制这些实例）并制作 2 个特定的 Book 实例，分别代表“最小的书”和“最大的书”。

这个技巧的好处是它允许在需要时添加更多维度。例如，您可以将年份添加为第二个维度，然后选择仅查找作者的书籍，或者查找特定年份的作者的书籍。当使用更多维度时，来自新 C++0x 的元组可能会变得很方便。

这个技巧还有一个好处是它可以保护你避免两次添加一本书。如果一本书被添加了两次，它仍然会在集合中出现一次（如果我们假设这本书的作者永远不会改变）。如果您要使用 multi_map，您可以将同一本书添加两次，这可能是不想要的。

于 2010-11-09T11:16:30.957 回答
1

您可以按照以下方式（但使用更合适的名称）做一些事情。请注意，输出结构实际上是集合的映射，而不是集合的集合，因为这样您就可以保留键。

#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;
}
于 2010-11-09T11:29:39.690 回答
1

这将创建一个集合映射。套套真的没有意义。

对于集合中的每个元素，您可以执行以下操作：

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[]。

于 2010-11-09T12:09:53.260 回答