c++ - 如何访问/迭代 unordered_multimap 中的所有非唯一键？

Question

我想访问/迭代 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() )并且内层循环测试相应的键是否多次出现。

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

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

Answer 1

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

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

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