如何使用组成排序键的位域而不落入UB？

Question

假设我想要以下位域：

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

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

union UnionSortKey {
    SortingKey key;
    uint8_t value;
}

但是，在 C++ 中，读取不活动的联合成员是未定义的行为。如何保证不掉UB但保持简单的整数比较？

Answer 1

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

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

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

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

之前，您必须手动提供conversion/comparison：

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);
}

如果幸运的话（位域是特定于实现的，所以...），您的编译器可能会对基础类型进行简单的比较。

（clang 成功地以“正确”顺序进行优化）。

或者，如果你没有填充bit/byte，你可以使用memcpy/memcmp（成功优化）

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;
}

Demo

如何使用组成排序键的位域而不落入UB？

How to use bitfields that make up a sorting key without falling into UB?

c++

undefined-behavior

unions

bit-fields