2

我想访问/迭代 unordered_multimap 中的所有非唯一键。哈希表基本上是从<SIG>实际上确实不止一次出现的签名到标识符的映射<ID>。我想在哈希表中找到那些出现一次的条目。

目前我使用这种方法：

// map <SIG> -> <ID>
typedef unordered_multimap<int, int>    HashTable;
HashTable& ht = ...;
for(HashTable::iterator it = ht.begin(); it != ht.end(); ++it)
{
    size_t n=0;
    std::pair<HashTable::iterator, HashTable::iterator> itpair = ht.equal_range(it->first); 
    for (   ; itpair.first != itpair.second; ++itpair.first) {  
        ++n;
    }
    if( n > 1 ){ // access those items again as the previous iterators are not valid anymore
        std::pair<HashTable::iterator, HashTable::iterator> itpair = ht.equal_range(it->first); 
        for (   ; itpair.first != itpair.second; ++itpair.first) {  
           // do something with those items
        }
    }
}

这当然不是有效的，因为外部循环遍历哈希表的所有元素（通过ht.begin()），内部循环测试相应的键是否存在不止一次。

有没有更有效或更优雅的方法来做到这一点？

注意：我知道使用 aunordered_map而不是unordered_multimap我不会有这个问题，但由于应用程序的要求，我必须能够存储多个<SIG>指向不同标识符的键<ID>。此外，anunordered_map<SIG, vector<ID> >对我来说不是一个好的选择，因为它使用了大约 150% 的内存，因为我有许多唯一的键，并且vector<ID>为每个项目增加了相当多的开销。

4

2 回答 2

2

用于std::unordered_multimap::count()确定具有特定键的元素数。这为您节省了第一个内部循环。

您无法阻止对整个HashTable. 为此，HashTable必须维护将基数映射到键的第二个索引。这将引入显着的运行时和存储开销，并且仅在少数情况下有用。

您可以使用 隐藏外循环std::for_each()，但我认为这不值得。

于 2013-05-31T07:15:09.733 回答
0

我认为您应该将数据模型更改为：

std::map<int, std::vector<int> > ht;

然后您可以轻松地遍历地图，并检查每个元素包含多少项size()

但在这种情况下，构建数据结构并以线性模式读取它有点复杂。

于 2013-05-31T07:17:09.000 回答