侵入式容器Intrusive container
把链接或索引节点嵌入被管理对象，由容器维护这些成员。
- 核心约束
- 容器中的每个链接必须属于仍存活且位置稳定的宿主对象。
- 适用问题
- 内核对象、任务队列、需要多重索引的系统对象管理。
- 边界与取舍
- 对象布局与容器耦合；摘除、移动、释放和并发访问需要明确规则。
常见操作#
n 为对象数；链接字段嵌入对象，操作由底层链表或树决定。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 对象与容器节点互相定位 | 已知内嵌链接的固定偏移；对象必须仍然存活。 | |
| 链表中插入 / 摘除已知节点 | 双向链表，不分配独立容器节点；不包含查找。 | |
| 红黑树中按键查找 / 插入 / 删除 | 比较成本为 ，维护平衡树不变量。 | |
| 遍历 | 遍历链接或树节点；容器不自动延长对象的生命周期。 |
时间与空间#
- 时间复杂度
- 取决于底层链表、树或哈希表
- 存储空间
每个成员关系仍需链接字段；省去的是独立节点和对应分配，不是所有索引空间。
工程中的应用#
2 个案例 · 附源码Linux 把 list_head 嵌入业务对象，通过成员偏移找回宿主，并在编译期检查指针类型。
附源码片段 · 内存管理
Linux 普通定时器把较近超时放进细粒度槽，远期超时放进粗粒度槽，使用位图寻找待处理槽。v6.12 的这套时间轮不再逐层级联迁移。
附源码片段 · 调度与资源分配
基础原理参考资料
Boost.Intrusive · Presenting containers分别说明侵入式链表、红黑树等容器的布局和操作成本。
Boost.Intrusive · Intrusive vs non-intrusive节点嵌入、无额外节点分配和对象生命周期责任。