logo标签列表

Boost中的位集映射到位集的无序（哈希）映射。

c++boosthashunordered-mapbitset
6

我希望从一个dynamic_bitset到另一个dynamic_bitset使用由Boost的unordered_map实现的缓存。问题在于，位集没有默认的哈希函数。这似乎不是一个概念上的问题，但我不知道如何解决技术细节。我该怎么做？

请访问https://svn.boost.org/trac/boost/ticket/2841。 - kennytm
我无法使用这个，因为 m.bits 是一个私有成员（建议对 dynamic_bitset 进行更改）。 - R S
m.bits 应该是公共常量，这很愚蠢！你能否使用 vector<bool>（它是一个工作更好的位集）作为键？ - Mahmoud Al-Qudsi
我正在使用位集(bitset)，因为我正在进行大量的集合计算(交集等)，这些计算在按位完成时要快得多。所以我想不是。 - R S
5个回答
6
我找到了一个意想不到的解决方案。原来boost有一个选项可以#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS。当定义了这个选项后，包括m_bits在内的私有成员变量就变成了公共的（我认为这是为了处理旧编译器或其他问题）。
现在我可以使用@KennyTM的答案，稍作修改：
namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {            
        return boost::hash_value(bs.m_bits);
    }
}
3

这是一个功能请求。

可以通过将位集转换为向量临时变量来实现一个不太高效的唯一哈希：

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {
        std::vector<B, A> v;
        boost::to_block_range(bs, std::back_inserter(v));
        return boost::hash_value(v);
    }
}
我该怎么使用它？我尝试了 "unordered_map<node_set, node_set, boost::hash<node_set> > cache;" 但它仍然无法编译。 - R S
3
有一个名为to_block_range的函数，它将位集包含的单词复制到某个缓冲区中。为了避免实际复制，您可以定义自己的“输出迭代器”，仅处理单个单词并从中计算哈希值。关于如何计算哈希：例如，参见FNV哈希函数。
不幸的是，dynamic_bitset的设计在我看来很愚蠢，因为它不直接提供对底层缓冲区的访问权限（甚至没有作为const）。
只需复制粘贴dynamic_bitset头文件并将其替换为“my_dynamic_bitset”，这真的很难吗？唯一的区别是它不再是私有的。 - R S
这是一个维护问题。每当主流文件因任何原因更新时，您都必须重复相同的过程。 - zvrba
2
我们无法直接计算哈希值，因为dynamic_bitset中的底层数据是私有的（m_bits）。
但我们可以轻松地通过绕过C++访问规范系统来解决这个问题，而不需要进行以下操作：
  • 修改代码或
  • 假装你的编译器不符合规范（BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS）
关键在于模板函数to_block_range，它是dynamic_bitset的朋友。因此，该函数的特化也可以访问其私有数据（即m_bits）。
最终的代码非常简单。
namespace boost {


// specialise dynamic bitset for size_t& to return the hash of the underlying data
template <>
inline void
to_block_range(const dynamic_bitset<>& b, size_t& hash_result)
{
    hash_result = boost::hash_value(bs.m_bits);
}

std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) 
{            
    size_t hash_result;
    to_block_range(bs, hash_result);
    return hash_result;
}
}
不幸的是，这似乎并不是真的。to_block_range函数的具体专业化是dynamic_bitset的友元。在保持友元函数访问权限的情况下，不可能有另一个同名但参数不同的函数。 - BSchlinker
@BSchlinker 我不同意：boost::dynamic_bitset 声明为： template <typename Block = unsigned long, typename Allocator = std::allocator<Block> > class dynamic_bitset; - Leo Goodstadt
原始的_befriended_模板函数是： template <typename B, typename A, typename BlockOutputIterator> friend void to_block_range(const dynamic_bitset<B, A>& b, BlockOutputIterator result); 因此，在 template <> inline void to_block_range(const dynamic_bitset<>&, tuple<unsigned, unsigned, unsigned long&>) 中的特化意味着 typename B = unsigned long，typename A = std::allocator<Block>，typename BlockOutputIterator = tuple<unsigned, unsigned, unsigned long&>。看起来像作弊，非常淘气...但是这是合法的C++。 - Leo Goodstadt
@BSchlinker。而且它能够编译！（GCC 4.8和clang 3.4） - Leo Goodstadt
0

在以下情况下，所提出的解决方案会生成相同的哈希值。

#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {            
        return boost::hash_value(bs.m_bits);
    }
}

boost::dynamic_biset<> test(1,false);

auto hash1 = boost::hash_value(test);

test.push_back(false);

auto hash2 = boost::hash_value(test);

// keep continue...

test.push_back(false);

auto hash31 = boost::hash_value(test);

// magically all hash1 to hash31 are the same!

对于哈希映射，所提出的解决方案有时不合适。

我阅读了dynamic_bitset的源代码，了解到dynamic_bitset与vector<bool>一样，每个值存储一个位。例如，您调用dynamic_bitset<> test(1, false)，那么dynamic_bitset最初分配4个字节，全部为零，并且它保存位的大小（在这种情况下，大小为1）。请注意，如果位的大小变得大于32，则会再次分配4个字节并将其推回到dynamic_bitsets<>::m_bits中（因此m_bits是4字节块的向量）。

如果我调用test.push_back(x)，它将第二位设置为x，并将位的大小增加到2。如果x为false，则m_bits[0]根本不会改变！为了正确计算哈希，我们需要在哈希计算中考虑m_num_bits。

那么问题是如何解决？

1：使用boost::hash_combine 这种方法简单直接。我没有检查这是否编译。

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
        size_t tmp = 0;
        boost::hash_combine(tmp,bs.m_num_bits);           
        boost::hash_combine(tmp,bs.m_bits);
        return tmp;
    }
}

2：翻转 m_num_bits % bits_per_block 位。 根据位数翻转一个位。我相信这种方法比1更快。

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {
        // you may need more sophisticated bit shift approach.
        auto bit = 1u << (bs.m_num_bits % bs.bits_per_block);
        auto return_val = boost::hash_value(bs.m_bits);

       // sorry this was wrong
       //return (return_val & bit) ? return_val | bit : return_val & (~bit);
       return (return_val & bit) ? return_val & (~bit) : return_val | bit;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接