如何使用组成排序键的位域而不落入 UB? [英] How to use bitfields that make up a sorting key without falling into UB?

问题描述

假设我想要以下位域:

struct SortingKey {
    uint8_t a: 2;
    uint8_t b: 4;
    uint8_t c: 2;
}

要使用简单的整数比较，我可能需要将它包装成这样的联合并使用 value 进行排序:

To use a simple integer comparison, I may need to wrap it into an union like this and use value for sorting:

union UnionSortKey {
    SortingKey key;
    uint8_t value;
}

然而，在 C++ 中，读取不活动的联合成员是未定义行为.如何保证不陷入UB而是保持简单的整数比较?

However, in C++, reading an inactive union member is Undefined Behaviour. How can I guarantee that I do not fall into UB but keeping a simple integer comparison?

推荐答案

你不能使用 union 进行类型双关，

You can't use union for type punning,

在 C++20 中，您可以使用默认的 operator <=>

In C++20, you might use default operator <=>

struct SortingKey {
    uint8_t a: 2;
    uint8_t b: 4;
    uint8_t c: 2;

    auto operator <=>(const SortingKey&) const = default;
};

之前，您必须手动提供转换/比较:

Before, you have to provide the conversion/comparison manually:

bool compare(SortingKey lhs, SortingKey rhs)
{
    if (lhs.a != rhs.a) return lhs.a < rhs.a;
    if (lhs.b != rhs.b) return lhs.b < rhs.b;
    return lhs.c < rhs.c;
}

或

bool compare(SortingKey lhs, SortingKey rhs)
{
    auto to_u8 = [](SortingKey s) -> std::uint8_t{ return s.c << 6 | s.b << 2 | s.a; };
    return to_u8(lhs) < to_u8(rhs);
}

如果幸运的话(位域是特定于实现的，所以...)，您的编译器可能会对底层类型进行简单的比较.

If you are lucky (bitfield is implementation specific, so...), your compiler might do a simple comparison of underlying type.

(clang 成功地以正确"的顺序进行了优化).

(clang succeeds to do that optimization with "correct" order).

或者，如果您没有填充位/字节，您可以使用 memcpy/memcmp(成功优化)

or, if you don't have padding bit/byte, you might use memcpy/memcmp (which succeeds to be optimized)

bool compare(SortingKey lhs, SortingKey rhs)
{
    auto to_u8 = [](SortingKey s) -> std::uint8_t{
        std::uint8_t c; memcpy(&c, &s, 1); return c;
    };
    return to_u8(lhs) < to_u8(rhs);
}

或

bool compare(SortingKey lhs, SortingKey rhs)
{
    return memcmp(&lhs, &rhs, 1) < 0;
}

演示

这篇关于如何使用组成排序键的位域而不落入 UB?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！