此篇博客的目标：

1.解释何为boost侵入式容器

2.利用boost侵入式容器实现根据不同变量做键来进行排序

一、什么是侵入式？

侵入式容器是一个相对的概念，其对立的就是非侵入式容器，比如STL的vector、map等。侵入式容器在此阶段可以简单的被想象成熟识的链表或者树。

一个例子：

一个对象有两个属性，抽象成 int a_; string b_;

如果要分别按两个属性有序存储以上五个实例

// 第一种以非侵入式容器vector

struct test{ int a_; string b_;

// 其他成员函数

};

test a,b,c,d,e; //初始化工作

std::vector<test> test_list1，test_list2; //两个队列以不同的成员排序

test_list1.insert(a);test_list2.insert(a);

test_list1.insert(b);test_list2.insert(b);

test_list1.insert(c); test_list2.insert(c);

test_list1.insert(d); test_list2.insert(d);

test_list1.insert(e);test_list2.insert(e);

// 第二种以侵入式链表实现

struct test{ int a_; string b_; test *a_next; test *b_next;

// 其他成员函数

};

test *a,*b,*c,*d,*e, *dummy; // 初始化工作(malloc)

a->a_next = b；b->a_next = c;.......// 按照a_排序

a->b_next = b; b->b_next = c;........// 按照b_排序

上面以一个例子建立关于侵入式容器和非侵入式容器的直观印象。根据以上例子，简单总结侵入式和非侵入式容器的区别：

1.侵入式容器的元素本身有除数据之外的属性，如指针。这样侵入式容器才成型。

2.非侵入式容器存储元素时要进行复制，如上面，以两种属性进行排序，声明两个容器，每个a,b,c,d,e实例都存在两份。而侵入式容器不涉及复制，内存只存在一份数据。

二、上面的例子以boost侵入式该怎么实现？

#include<intrusive/...> // 引入相关库文件

strcut test{ int a_; string b_;

slist_member_hook<> a_hook_; // 为按照a_排序声明的挂钩，相当于前面的a_next；

slist_member_hook<> b_hook_; // 为b_声明的挂钩......

// a_和b_各自的比较函数(比较函数可以声明定义在外部)

struct a_compare{bool operator()(const test &l, const test &r){return l.a_ < r.a_;}};

struct a_compare{bool operator()(const test &l, const test &r){return l.a_ < r.a_;}};

};

// 以a_作比较的容器

typedef member_hook<test, slist_member_hook<>, &test::a_hook_> a_option;

typedef slist<test, a_option, compare<test::a_compare>> a_list;

// 以b_作比较的容器

typedef member_hook<test, slist_member_hook<>, &test::b_hook_> b_option;

typedef slist<test, b_option, compare<test::b_compare>> b_list;

test a,b,c,d,e; //初始化

// a_和b_容器的使用

a_list.push_back(a); b_list.push_back(a);

a_list.push_back(b); b_list.push_back(b);

a_list.push_back(c); b_list.push_back(c);

a_list.push_back(d); b_list.push_back(d);

a_list.push_back(e); b_list.push_back(e);

可以看到，设计完成的侵入式容器在使用上和非侵入式容器一致，但是其本质上还是侵入式容器，即a,b,c,d,e虽然以不同成员变量做排序但是内存中其只有一份数据。

boost库的intrusive有两种使用方法，之一是上面用到的方法以成员变量的形式被声明于类中，称为挂钩；另一种是以基类的方式被用户继承实现。

三、生产环境中boost/intrusive的使用

至此，boost/intrusive的基本使用介绍完毕，下面以一个例子详细展示其使用细节。

现在有一个需求，其实就是分布式计算平台的内部数据结构：

1.每当Master服务器收到新的计算节点的上线连接请求时，为每个请求分配一个唯一的id，并且将其id和对应的ip保存起来。此过程是计算节点的注册过程

2.当有若干个计算任务到来时，将若干个任务分配到已经注册的节点。由计算节点来执行具体的计算任务。

非侵入式设计

那么在非侵入式容器背景下，数据结构的设计可能会是如下所示：

首先创建一个map<int, string> slaveList，用以保存所有注册的计算节点。int是节点id，string是节点ip。然后为了记录每个计算任务被分配到哪一个计算节点，再创建一个map<int, int> allocateList，key是计算任务的id，value是计算节点id。最后为了效率问题，需要一个队列来保存每个计算节点在运行哪些任务，所以创建multimap<int, int> loadList，key是计算节点id，vlaue是任务id。

那么当计算节点的某个任务完成之后，就可以删除allcoateList和loadList对于的任务；当计算节点宕机，删除slaveList相应字段，并删除allocateList和loadList相应的任。

以上就是非侵入式容器的设计思路。