c++ - boost::unordered_multimap:有效地获取桶中的所有元素？

Question

我可以使用这段代码将所有元素放入一个桶中:

typedef boost::unordered_multimap< key, myClass*, MyHash<key> >
                                                HashMMap;
HashMMap::iterator it;
it = hashMMap_.find( someKey);
int bucketIndex = hashMMap_.bucket( someKey);
int bucketSize = hashMMap_.bucket_size( bucketIndex);

qDebug() << "index of bucket with key:" << someKey << " is:"
         << bucketIndex;
qDebug() << "number of elements in bucket with index:" << bucketIndex << " is:"
         << bucketSize;

HashMMap::local_iterator lit;
/* begin of bucket with index bucketIndex */
lit = hashMMap_.begin( bucketIndex);

for ( ; lit != sender_.hashMMap_.end( bucketIndex); ++lit) {
    qDebug() << "(*lit).first:" << (*lit).first << ", (*lit).second:" <<
               (*lit).second << ", (*lit).second->something_:" <<
               (*lit).second->something_;
}

我想得到一个 local_iterator 到桶中的第一个元素并迭代它直到桶结束，所以如果哈希表中的给定索引只有一个值(其中索引是 Hash(key) )我将仅遍历单个元素并接收 bucket end()，如果有许多元素，我将遍历整个 bucket(所有值具有相同的哈希值)。如果没有 bucketIndex 这可能吗？ , hashMMap_.begin( bucketIndex)和 hashMMap_.end( bucketIndex) ？

所以基本上我想要一个像这样的 local_iterator:

HashMMap::local_iterator lit = hashMMap_.find_bucket_if_present( someKey);

---

另外一个问题是:如果 find() 是否必须先测试在调用 int bucketIndex = hashMMap_.bucket( someKey) 之前返回元素的迭代器？这是我的想法，因为 bucket() 的解释 boost 网站的功能是:

Returns: The index of the bucket which would contain an element with key k.

                                 ^^^

我认为这意味着我必须先到 find(key)在 multimap 中知道键是否存在，因为调用 bucket(key)将在哈希表中返回一个索引，该索引不是哈希而是哈希的模( bucket_from_hash )，如果存在，则存储在该哈希表中。所以因为用 bucket_count 完成的模数，如果未插入 key ，我将遍历当前情况下它所在的虚拟存储桶，这对我来说最重要的是:也可能存在不同的哈希值，因为 bucket_count 可能小于我的哈希值(我使用 16- 32 位 key 的位 MyHash<key> 作为哈希函数提供给 multimap 构造函数)。这是正确的吗？

Answer 1

我会像这样开始使用范围:

template<typename BoostUnorderedMap, typename Key>
boost::iterator_range< typename BoostUnorderedMap::local_iterator > get_bucket_range( BoostUnorderedMap& myMap, Key const& k ) {
  int bucketIndex = myMap.bucket( k );
  return boost::iterator_range< typename BoostUnorderedMap::local_iterator >(
    myMap.begin(bucketIndex),
    myMap.end(bucketIndex)
  }
}
template<typename BoostUnorderedMap, typename Key>
boost::iterator_range< typename BoostUnorderedMap::local_const_iterator > get_bucket_range( BoostUnorderedMap const& myMap, Key const& k ) {
  int bucketIndex = myMap.bucket( k );
  return boost::iterator_range< typename BoostUnorderedMap::local_const_iterator >(
    myMap.begin(bucketIndex),
    myMap.end(bucketIndex)
  }
}

然后，至少在 C++11 中，您可以执行以下操作:

for (auto && entry : get_bucket_range( some_map, "bob" ) )

它会遍历 “bob” 存储桶中的所有内容。

虽然这确实使用了 bucketIndex，但它向最终消费者隐藏了这些细节，而只是为您提供了一个 boost::range。