浅谈侵入式容器

鉴于C++标准库并没有提供侵入式容器供我们使用，这里只简单梳理一下侵入式容器的特性

最简单的侵入式容器

先看一个最简单的示例：list_head

struct list_head {
    list_head *prev, *next;
};

这是Linux提供的内核链表，一个最简化的侵入式容器

可以与非侵入式STL风格的实现对比一下

template <typename Tp>
struct ListNode {
    ListNode *prev, *next;
    Tp value;
    // ...
};

相比于STL风格的区别，可以看出list_head不维护value，

使用的话是这种画风

struct Foo {
    int value;
    list_head link; // 指向另外两个Foo类的的list_head link
};

// 区别于
ListNode<int> bar; // 可以指向另外的&ListNode<int>

这就是侵入式容器的全部区别了吗？我们再琢磨一下

泛型支持

非侵入式的ListNode对于不同类型的value，需要提供真正意义上不一样的类型ListNode<T>

但是list_head并不需要维护多余的泛型typename，list_head就是任意类型兼容的容器

ListNode<FoOO> n1;
ListNode<Foooo> n2;

也许对于C++并没什么，但是对于不支持泛型的语言来说这种设计绝对是个优势

另外从生成的实例类型来说，也可带来编译成本的减小

PS. 并不是说所有侵入式容器就会抛弃泛型，像boost::intrusive套餐就还是得带上typename

空间分配

STL的容器都是搭上allocator来维护内部element的分配/销毁，由于allocator是放在template上的（不考虑std::pmr），所以造成了allocator注定是无状态的~~（什么是无状态，简单点说就是用了等于白用）~~，大部分情况来说，它就是一个new+ctor的解耦与抽象，问题就是new，不管怎样，它只有一种选择，看下面例子

template <typename Tp, typename Allocator>
struct List {
    ListNode<Tp> *mData; // 由Allocator分配
    // ...
};

大部分情况下，不管List是放在堆还是栈，mData分配的基本只能是在堆上，你没有选择的余地，因为allocator不能运行时更改，它的策略已经是编译时决定好了

相比之下，list_head是如何分配的，完全取决（绑定）于调用方FOooOoO，可以直接在栈上分配，也可以一并new FOooOoO放到堆上

struct FOooOoO {
    std::string name;
    int uid;
    list_head link;
};
auto pf1 = new FOooOoO(/*...*/);
FOooOoO f2(/*...*/);

分离的地址

前面提到new分配的问题，非侵入式容器也有缺点，它们可能会至少new两次

考虑new List过程

auto pList = new List<int>(/*size*/1, /*value*/ 100);

由于内部mData是额外分配的，因此&pList与pList.mData指向是分离的

这有什么问题？cache律师表示这样不好，因为这样不容易利用cacheline

至于list_head是不需要考虑这些问题，空间本身是与调用方连续的

补充：并非如此

难道这个缺点，非侵入永远没法克服吗？

不是的，可以看下智能指针std::make_shared过程如何处理这种分离的分配问题，它可以做到Tp和引用计数块绑定在一起连续分配，当然这很需要技巧性

引用计数老问题

前面提到智能指针，那就顺便提一个非侵入式智能指针的经典错误

auto pValue = new F00(/*...*/);
std::shared_ptr<F00> p1(pValue);
std::shared_ptr<F00> p2(pValue); // oops

原因在于引用计数块是在std::shared_ptr容器内部的，与pValue完全独立，因此会有两个引用计数块来处理同一个值引起错误的RAII

那么侵入式的智能指针会有这个问题吗？

boost::intrusive_ptr使用是这样的，它把引用计数与内部实现绑定在一起

struct FoOo: public boost::intrusive_ptr_base<FoOo> { // 含有引用计数ref_count
    int age;
    std::string name;
};

auto pValue = new FoOo();
boost::intrusive_ptr<FoOo> p1(pValue);
boost::intrusive_ptr<FoOo> p2(pValue); // 由同一个来自pValue的refcount来维护

容易看出，侵入式智能指针是通过绑定到FoOo内部的refcount来实现正确的引用计数

抽象与复用

侵入式容器在抽象与复用的层面上是有显然的不足的，

考虑一下，如何用list_head表示出list of list of list的数据结构，

非侵入式只需要list<list<list<Tp>>>就足够了

对于复用，这是最突出的问题，每个实现都要写一份才像样，侵入式容器最多能做到这种程度

class Type: public IntrusiveContainer {
    // ...
};

能不能给力点，也许mixin可以吧（用魔法打败魔法，滑稽.jpg）

template <typename ...Ts>
class Mixin: public Ts... {};
// Mixin<Type, IntrusiveContainer> fOoooo;

总结

合适的时机使用合适的容器，多一种选择是件好事。

简单来说，侵入式容器的独特设计可以带来以下特性

数据结构拥有更加紧凑的内存空间，且灵活的分配与更加受控的生命周期都更易于提高性能
虽然在类型表达能力与非侵入相比有所不足，但是可以与具体类型解耦
更易于实现本身依赖于具体类型的特性