1

我想在 C++ 中有一个用户定义的键std::map。关键是具有最大值的整数集的二进制表示，2^V因此我无法表示所有2^V可能的值。我通过有效的二进制集表示来做到这一点，即uint64_t.

现在的问题是，要将这个用户定义的位集作为 a 中的键std::map，我需要定义位集值之间的有效比较，但是如果我的最大大小为 ，V=1000那么我无法得到一个可以比较的数字，让单独聚合它们2^1000是不可表示的。

因此我的问题是，假设我有两个不同的集合（通过在我的位集表示中设置正确的位）并且我不能表示最终数字，因为它会溢出：

id_1 = 2^0 + 2^1 + ... + 2^V

id_2 = 2^0 + 2^1 + ... + 2^V

是否有合适的转换会导致我可以比较的值？我需要能够这么说id_1 < id_2，所以我想将指数总和转换为一个可表示的值，但保持“小于”的不变量。我正在考虑例如以一种聪明的方式应用对数转换来保留“小于”。

这是一个例子：

set_1 = {2,3,4}; set_2 = {8}

id(set_1) = 2^2 + 2^3 + 2^4 = 28; id(set_2) = 2^8 = 256

id(set_1) < id(set_2)

完美的！一个可以有 的一般集合，{1,...,V}因此2^V有可能的子集怎么样？

4

1 回答 1

4

我通过一个有效的二进制集表示来做到这一点，即 uint64_t 的数组。

假设这个数组是通过rakey type的数据成员访问的Key，并且两个数组都是 length N，那么你需要一个像这样的比较器：

bool operator<(const Key &lhs, const Key &rhs) {
    return std::lexicographical_compare(lhs.ra, &lhs.ra[N], rhs.ra, &rhs.ra[N]);
}

这隐含地认为数组是大端的，即第一个uint64_t是最重要的。如果您不喜欢这样，那很公平，因为您可能已经考虑V到您将位存储到数组中的任何顺序的相对重要性。没有什么大不了的lexicographical_compare，所以只需看一个示例实现并根据需要进行修改。

这被称为“字典顺序”。除了我使用uint64_t而不是char两个数组长度相同的事实之外，这是比较字符串的方式[*] - 实际上使用uint64_t并不重要，您可以只std::memcmp在比较器中使用而不是比较64 位块。operator<for strings 不能通过将整个字符串转换为整数来工作，你的比较器也不应该。

[*] 直到您使用特定于语言环境的排序规则。

于 2012-10-04T10:29:40.783 回答