c++ - bool 内存高效链表

Question

您将如何实现一个内存高效的 bool 链表？显然下一个节点指针比常规链表中的有效负载本身大得多。

Answer 1

在大于 1 字节的边界上对齐节点，并使用“下一个”指针的最低有效位对 bool 值进行编码。

我不太擅长直接在文本框中编写代码，但大致如下:

struct node {
    static_assert(alignof(node) > 1, "node is insufficiently aligned");

    bool get_value() const {
        return static_cast<bool>(reinterpret_cast<size_t>(next) & 0x1);
    }

    void set_value(bool value) {
        size_t ptr = reinterpret_cast<size_t>(next);
        ptr &= ~1;
        ptr |= static_cast<size_t>(value);
        next = reinterpret_cast<node*>(ptr);
    }

    node* get_next() const {
        size_t ptr = reinterpret_cast<size_t>(next);
        ptr &= ~1;
        return reinterpret_cast<node*>(ptr);
    }

    void set_next(node* n) {
        bool value = get_value();
        next = n;
        set_value(value);
    }

private:
    node* next;
};