布尔内存高效链表

Question

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

Answer 1

这是一个大概的想法。在您的链表节点中，有两个字段，第一个是指向下一个节点的指针，第二个是另一个与您系统上的指针大小相等的整数成员。例如，在 64 位架构上：

struct node {
  node *next;
  uint64_t bits;
}

然后每个节点存储 64 个布尔值，而不仅仅是标准链表实现中的一个。许多操作的时间效率降低（但这是 memory/space 效率的通常折衷），因为当您添加第 65 个布尔值或插入 [=19 时，您将不得不进行一些位移和类似于树平衡的操作=] bitset 等（此外，进一步考虑，您可能需要第三个成员告诉您使用的位数。）

但是，这有一些优点，因为像这样的简单结构非常适合缓存。

就像我说的，这只是一个粗略的想法，实施这样的事情可能会有很多陷阱。编写好的测试。

Answer 2

在大于 1 字节的边界上对齐节点，并使用 'next' 指针的最低有效位对 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;
};

布尔内存高效链表

Boolean memory efficient linked list

c++

data-structures

c++17