侵入式容器 Boost.Intrusive

Boost.Intrusive 是一个很有意思的实现，里面实现了很多侵入式容器，在特定环境下，可以大大提升性能。

首先我们得理解什么是侵入式，什么是非侵入式。普遍，我们认为std的容器，比如std::list都是非侵入式的。这是因为对于任何一个（支持复制或者移动的）类型T，我们都可以定义std::list<T>。当往std::list里插入一个元素时，它会分配一个节点，这个节点的结构类似于下面这个：

struct Node {
    T data;
    Node* prev;
    Node* next;
};

std::list会将要插入的元素复制到节点里。

如果T很大，那么std::list<T>将在复制时产生较大的代价。有没有一个方法可以避免复制元素呢？或者如果T是不可复制和移动的元素呢？一个直接的方法是std::list<T*>，链表里只保存元素指针，这样只复制一个指针就好了，像是解决了我们的问题。

但 Boost.Intrusive 走得更远一些。原因是，std::list<T*>在插入元素时，还是会去分配一个节点（虽然这个节点很小只有三个指针），这产生了新的内存申请！而我们知道内存申请是很慢的，应该尽量避免。Boost.Intrusive 提供的类似容器boost::intrusive::list可以做到完全不用分配节点。

听上去很神奇，但说穿了并不神秘。 回到上面的节点，事实上，我们只需要原始数据类型T里面含有这两个节点指针就可以了！比如T的定义如下：

struct T {
    int age;
    std::string name;
    T* prev;
    T* next;
};

这使得boost::intrusive::list实现的链表非常简单，它只用保存首尾两个元素的地址。所有操作都无需任何额外的内存分配。示例代码如下：

template<class T>
class boost::intrusive::list {
    T* front;
    T* back;

public:
    void push_back(T& t) {
        if (back == nullptr) {
            back = front = &t;
        }
        else {
            back->next = &t;
            t.prev = back;
            back = &t;
        }
    }

    void pop_back() {
        T* top = back;
        back = back->prev;
        top->prev = nullptr;
    }
}

这要求基础数据类添加辅助元素，相当于容器「入侵」了数据，所以叫做侵入式容器。Boost.Intrusive 提供多个侵入式容器，最常用的是下面两个：

• list: std::list的侵入式版本。用户数据需添加两个指针。大部分操作都是O(1)时间。
• set/multiset/rbtree: std::set/std::multiset的侵入式版本，基于红黑树。用户数据需添加三个指针。大部分操作都是O(log n)。

而用户定义支持 Boost.Intrusive 的数据类，并不需要手工去添加T* prev, next之类的（前面只是示例）。库提供基类直接继承即可。比如要支持boost::intrusive::list，直接继承boost::intrusive::list_base_hook基类即可:

struct T : public boost::intrusive::list_base_hook<> {
    int age;
    std::string name;
};

该基类本身可以带模板参数，有很多细节可以定义。比如有一个有意思的基类是using auto_unlink_hook = list_base_hook<link_mode<auto_unlink>>。当用户数据使用它做基类数，当插入到链表里的数据析构时（注意链表并不保存数据，因此两者有不同的生命周期），将自动从链表里删除，从而避免在链表里访问到无效的数据。

Q. E. D.