嵌入式现代C++教程——侵入式容器设计¶

你记得普通容器对数据做什么吗？拷贝指针、分配节点、维护额外的内存布局，然后在某个时刻默默地吃掉你的缓存局部性。侵入式容器则更直白：数据对象自己把手伸出来当链表节点——谁要付额外内存和间接访问？不是我。

什么是侵入式容器，为什么在嵌入式特别香¶

侵入式（intrusive）容器的关键点：节点信息（next/prev/…）直接放在用户对象内部，而不是另外分配一个 node 包裹对象指针。优点显而易见：

零额外分配 —— 不需要每次 push 都 malloc/new 一个 wrapper（非常重要）。
更佳缓存局部性 —— 对象和元信息在一起，遍历更快。
更小的内存占用与确定性 —— 对于内存受限或实时系统非常友好。

缺点也很直接：

对象被耦合到容器接口（侵入），源码要修改对象结构。
一个对象要同时在多个链表中，需要多个“hook”成员或多继承。
使用不当会出现悬挂指针/重复插入等问题，需要更谨慎的生命周期管理。

适用场景：任务调度器、空闲块链表、驱动链表、内核/RTOS 数据结构、内存池的 free-list 等。

两种常见实现策略¶

基类 hook（inheritance）：对象继承一个包含 next/prev 的 hook 基类。类型安全，转换容易。
成员 hook（member hook）：对象包含一个 hook 成员（更灵活，可同时有多个 hook 实例），但是需要 container_of 技巧把 hook 指针转换回对象指针。

下面我们先实现一个干净的、可直接使用的“基类 hook”双向链表（适合教程和嵌入式），再说 member-hook 的思路与注意点。

代码：简单、类型安全的侵入式双向链表（继承式）¶

下面的实现目标：小而清晰，C++11 可用，适合嵌入式编译器。

// intrusive_list.h
#pragma once
#include <cassert>
#include <iterator>

// Intrusive list node base — 继承它即可成为链表节点
template<typename T>
struct IntrusiveListNode {
    T* prev = nullptr;
    T* next = nullptr;
};

// Intrusive doubly linked list
template<typename T>
class IntrusiveList {
public:
    IntrusiveList() : head(nullptr), tail(nullptr) {}

    bool empty() const { return head == nullptr; }

    void push_front(T* node) {
        assert(node && node->prev == nullptr && node->next == nullptr && "节点必须处于未链接状态");
        node->next = head;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }

    void push_back(T* node) {
        assert(node && node->prev == nullptr && node->next == nullptr && "节点必须处于未链接状态");
        node->prev = tail;
        if (tail) tail->next = node;
        tail = node;
        if (!head) head = node;
    }

    T* pop_front() {
        if (!head) return nullptr;
        T* n = head;
        head = head->next;
        if (head) head->prev = nullptr;
        else tail = nullptr;
        n->next = n->prev = nullptr;
        return n;
    }

    void erase(T* node) {
        assert(node && "erase null");
        if (node->prev) node->prev->next = node->next;
        else head = node->next;

        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;

        node->prev = node->next = nullptr;
    }

    void clear() {
        T* cur = head;
        while (cur) {
            T* nxt = cur->next;
            cur->prev = cur->next = nullptr;
            cur = nxt;
        }
        head = tail = nullptr;
    }

    // 简单迭代器（只读/可写）
    struct iterator {
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        explicit iterator(T* p) : p(p) {}
        reference operator*() const { return *p; }
        pointer operator->() const { return p; }
        iterator& operator++() { p = p->next; return *this; }
        iterator operator++(int) { iterator tmp = *this; ++*this; return tmp; }
        bool operator==(const iterator& o) const { return p == o.p; }
        bool operator!=(const iterator& o) const { return p != o.p; }
    private:
        T* p;
    };

    iterator begin() { return iterator(head); }
    iterator end() { return iterator(nullptr); }

private:
    T* head;
    T* tail;
};

如何使用：

// example.cpp
#include "intrusive_list.h"
#include <iostream>

struct Task : IntrusiveListNode<Task> {
    int id;
    Task(int i): id(i) {}
};

int main() {
    IntrusiveList<Task> runq;
    Task a(1), b(2), c(3);

    runq.push_back(&a);
    runq.push_back(&b);
    runq.push_front(&c); // 链表顺序： c, a, b

    for (auto &t : runq) {
        std::cout << "Task " << t.id << "\n";
    }

    runq.erase(&a);

    if (auto p = runq.pop_front()) {
        std::cout << "pop " << p->id << "\n";
    }
}

这段代码可以直接编译到嵌入式支持的 C++ 编译器（只要支持基础模板与 nullptr）。

成员 hook：当对象需要在多个链表中出现时¶

继承式简单，但如果一个对象需要同时属于多个链表（例如同时在 ready_list 和 wait_list），你需要多个 hook 成员或使用成员 hook 的方式。

成员 hook 的关键是 container_of —— 给定指向 hook 成员的指针，计算回包含它的对象指针（Linux 内核常用宏）。

简单的宏版实现（清晰且常用）：

#include <cstddef> // offsetof
#define CONTAINER_OF(ptr, type, member) \
    ((type*) ( (char*)(ptr) - offsetof(type, member) ))

示例结构：

struct MyObject {
    IntrusiveListNode<MyObject> ready_hook;   // for ready list
    IntrusiveListNode<MyObject> wait_hook;    // for wait list
    int data;
};

// 操作 ready list 时，将传入 &obj->ready_hook，然后用 CONTAINER_OF 转回 MyObject*

成员 hook 比较灵活，但使用时需特别注意：offsetof 要与实际成员名一致；并且强烈要求插入前检查该 hook 是否已经链接（避免重复插入）。

设计建议与防坑指南¶

对象生命周期必须明确：链表中的节点在被销毁前必须先从所有链表中移除。否则会出现野指针，后果通常是难以定位的崩溃。
插入前检查状态：给 hook 加一个 bool linked 字段或断言，防止重复插入。测试代码里多用 assert。
多 hook 需求优先使用成员 hook：若对象在多个容器间切换频繁，成员 hook 更灵活。
并发场景小心内存屏障/原子性：如果要在 ISR 或多核中操作链表，必须采用锁、原子 CAS 或者专门的 lock-free 算法（超出本篇范畴）。
提供 RAII wrapper：考虑提供一个小的 IntrusiveListGuard 或 ScopedUnlink 来保证异常或早返回时对象能安全注销。嵌入式代码也许没有异常，但 RAII 有助于写出更安全的释放代码。
调试信息：在开发阶段，把节点状态打印出来（id/地址/prev/next）能快速定位错误。
不要滥用：侵入式容器并非万能工具。若你不在乎每次分配开销或者对象不可修改（第三方库），就别侵入对象，普通 std::list/vector 更简单、安全、易维护。

何时该选择侵入式容器¶

在嵌入式 / 内核 / 实时系统，资源与延迟是第一要务，侵入式数据结构在这些场景是非常自然的选择。特别适合：

要求确定性、避免堆分配的系统（bootloader、RTOS kernel）。
需要高性能的 free-list、task queue、timer wheel 等。
想要最小内存占用的场景。

如果你做的是普通应用层业务逻辑，或者对象来自第三方库（无法改结构），侵入式方案的维护成本可能高于收益。

结语¶

侵入式容器的思想不复杂：让数据自己负责“站位”。但这要求你对对象的责任更清晰——谁插它、谁删它、什么时候删它。把责任写成代码，再把代码写成规范。对嵌入式系统而言，这是一种非常“实在”的工程哲学：省一分内存，多一分确定性。