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() 隐藏外循环，但我认为不值得。