我有一个multimap，想要得到一组集合 - 这些集合将多重映射中所有类型为A的项目按照相同的键分组在一起。STL中是否有内置的方法来实现这个功能？
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;
}
或者类似于此类的东西。
- vitaut
1
如果您的原始多重映射中有很少的唯一值，那么这个解决方案效果很好。这是O（M log N），其中M是唯一值的数量，N是整个多重映射的大小。因此，如果您有1,048,576个值和1024个唯一值（因此我们将创建1024个每个1024个条目），则与遍历原始列表时获得的O（N）相比，这是20K次比较（尽管您仍然需要遍历所有条目以插入到您的std :: sets中）。 - CashCow
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));
现在只需在下限和上限之间迭代，即可获取该作者的所有书籍。
这个技巧依赖于我选择存储指向书籍的指针，并且我知道最小和最大指针是什么（对于64位应用程序，您需要更改此内容！）。我必须承认这不是最好的技巧。
稍微好一点的替代方案是存储书籍本身（如果允许在应用程序中复制这些实例），并创建两个特定的Book实例，分别表示“最小的书”和“最大的书”。
这个技巧的好处是，它允许添加更多维度。例如，您可以将年份作为第二个维度添加，然后选择仅查找作者的书籍，或者查找特定年份的作者的书籍。使用更多维度时，新的C++0x元组可能会很方便。
这个技巧还有一个优点，它可以保护您免受重复添加书籍的影响。如果一本书被添加两次，则集合中仍将只有一本书（如果我们假设该书的作者永远不会改变）。如果您使用multi_map，则可能会添加相同的书两次，这可能是不想要的。
- Patrick
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;
}
- Bowie Owens
1
这将创建一个集合的映射。集合的集合并没有实际意义。
对于您的每个集合中的元素，您可以执行以下操作：
our_map[iter->first].insert(iter->second);
如果您有迭代器或
our_map[p.first].insert(p.second);
使用value_type对进行配对。
无论如何，对outer_set的operator[]会在未找到iter->first键时创建一个空的inner set，并在键已存在时检索现有的内部集合。
这样做是可行的，但效率不高。原因在于我们知道p.first要么匹配我们上次看到的最后一个键，要么必须插入到末尾，但以上代码每次都要进行查找。因此较为高效的方式是保留我们的set迭代器。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返回的pair中的第一个元素。
如果您不想使用迭代器，则可以像这样使用指向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[]。
- CashCow
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
std::map<key, std::vector<value>>呢？因为set的元素必须是const，所以使用起来可能会很困难... - Matthieu M.