侵入式容器 Boost.Instrusive

作者: , 共 1925 字 , 共阅读 0

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

首先我们得理解什么是侵入式,什么是非侵入式。普遍,我们认为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.Instrusive 走得更远一些。原因是,std::list<T*>在插入元素时,还是会去分配一个节点(虽然这个节点很小只有三个指针),这产生了新的内存申请!而我们知道内存申请是很慢的,应该尽量避免。Boost.Instrusive 提供的类似容器boost::instrusive::list可以做到完全不用分配节点。

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

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

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

template<class T>
class boost::instrusive::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.Instrusive 提供多个侵入式容器,最常用的是下面两个:

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

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

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

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

Q. E. D.

类似文章:
编程 » C++, Boost, 智能指针
如果理解了侵入式容器,侵入式智能指针也很容易理解。传统的智能指针std::shared_ptr使用了和数据无关的引用计数,这带来两个问题:
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::small_vector,代码文件地址:https://github.com/facebook/folly/blob/master/folly/small_vector.h
编程 » C++, 智能指针
前面已经提到std::shared_ptr有三个缺陷:
相似度: 0.136
boost是除std外最常用的 C++库,覆盖很多常用操作。目前最新的版本是1.59.0
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::sorted_vector_setfolly::sorted_vector_map,是std::mapstd::set在小数据集上的优化版。代码见: https://github.com/facebook/folly/blob/master/folly/sorted_vector_types.h
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样,folly::dynamic只支持保存以下几种类型:
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中,所有的dict都保留了插入顺序。但在 C++中,无论是std::map还是std::unordered_map,都没有保留插入顺序。当遍历时,std::map得到的是一个根据键值排序的有序序列,而std::unordered_map则基本是乱序。
编程 » C++, 智能指针
理论上而言,当 C++提供了std::unique_ptr, C++的程序就不应该出现普通指针了。所有普通指针都可以用std::unique_ptr代替,避免手动删除对象。
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中,所有的dict都保留了插入顺序。但在 C++中,无论是std::map还是std::unordered_map,都没有保留插入顺序。当遍历时,std::map得到的是一个根据键值排序的有序序列,而std::unordered_map则基本是乱序。
编程 » C++, C++11
花括号初始化是C++11引入的一种初始化方法。
智能指针在现代 C++里用得越多。以前只知道它大致的原理,比如使用引用计数。但很多实现细节并不清楚,最直接的,它是如何实现多线程安全的?今天找了 gnu c++ library 的实现好好看了一下。
编程 » C++, Boost, 智能指针
如果理解了侵入式容器,侵入式智能指针也很容易理解。传统的智能指针std::shared_ptr使用了和数据无关的引用计数,这带来两个问题: