《C++11/14高级编程：Boost程序库探秘》笔记

侵入式容器也是用于容纳元素的容器，但元素必须要做出一些代码上的适度修改才能被容纳。与侵入式容器相对应的是非侵入式容器，标准容器和指针容器都属于非侵入式容器，这类容器不要求对容纳的元素做任何修改即可容纳，较温和，用起来也简单方便。链表、二叉树等数据结构都属于侵入式容器。
侵入式容器虽然较非侵入式容器使用起来复杂麻烦，但是它没有非侵入式容器的拷贝、克隆等要求，也可以保存抽象类，对内存管理的要求很低，而且允许定制数据结构，所以通常能提供更好的性能。

Boost库intrusive重新引入了侵入式容器，具有近似标准容器的接口，大大降低了应用的难度。

---

从数据结构引入侵入式容器

手工实现链表
实现一个单向链表结构，这是一种最简单的侵入式容器。

class point :boost::noncopyable //简单的节点类，不可拷贝和赋值
{
public:
    int x, y;                   //节点的有效载荷

    typedef point*  node_ptr;   //指针类型定义
    node_ptr        next;       //后继指针

    point(int a = 0, int b = 0) :
        x(a), y(b), next(nullptr) {}

    node_ptr get_next()         //获得后继节点
    {
        return next;
    }

    void set_next(node_ptr p)   //设置后继节点
    {
        next = p;
    }
};

int main()
{
    point p1, p2(2, 2), p3(3, 3);   //三个节点对象，未连接

    p1.set_next(&p2);               //p1->p2
    p2.set_next(&p3);               //p1->p2->p3

    for (point::node_ptr p = &p1;   //指向头节点
        p != nullptr;               //终止条件
        p = p->get_next())          //指针前进到下一个节点
    {
        std::cout << p->x << "-" << p->y << "";
    }

    p1.set_next(&p3);               //从链表中移除p2，p1->p3

    return 0;
}

这里体现了侵入式容器的一些重要特性：

1. 元素除了自身必备的功能外还必须要增加一些额外的功能（这里指后继节点的指针）才能被容纳入侵入式容器（链表）
2. 侵入式容器不分配内存，元素的创建是容器之外的事。
3. 侵入式容器并不真正的”容纳“对象，元素仍然散落在内存中各个位置，仅仅是使用指针以某种算法（这里是单向顺序算法）把它们连接起来便于访问，某种程度上可称为”链接视图“。
4. 侵入式容器的插入删除等操作也只是操纵链接的指针，调整元素的链接顺序，不涉及内存的分配管理。

intrusive库介绍
intrusive库提供的侵入式容器都具有与标准容器类似的接口，主要有以下几种：

• slist：单向链表
• list：类似std::list的双向链表，是最常用的侵入式容器
• set/rbtree：基于红黑树，类似std::set的关联容器
• avl_set/avltree：基于AVL树，类似std::set的关联容器
• splay_set/splaytree：基于splay树，类似std::set的关联容器
• sg_set/sgtree：基于scapegoat树，类似std::set的关联容器
• treap_set/treap：基于堆二叉树，类似std::set的关联容器
• unordered_set：无序关联容器

根据侵入的程度这些容器又可以分为纯侵入式容器和半侵入式容器。大多数容器都属于纯侵入式容器，仅仅调整节点中的链接指针，没有“容纳”任何东西。无序关联容器unordered_set属于半侵入式容器，这是因为它需要一个额外的内存空间来维护散列容器所需的负载因子，不是完全的侵入。

侵入式容器的一个重要特点是它不负责管理元素的生命周期，仅仅是调整指针的链接，因此没有对象拷贝的运行开销，元素的创建工作是外部做的，最小化了内存使用，提高运行效率。

---

入门示例

使用侵入式容器必须要改变自有类的定义，为此，intrusive库提供了挂钩(hook)这一工具类，可以近似理解为链接指针的聚合。挂钩可以分为基类挂钩和成员挂钩两类，可以以基类或者成员的方式嵌入到自有类中使用。

1.使用基类挂钩

单链表侵入式容器使用的基类挂钩是slist_base_hook，改写point类：

#include <boost/intrusive/slist.hpp>
using namespace boost::intrusive;

class point :public slist_base_hook<>   //使用基类挂钩，缺省配置
{
public:
    int x, y;                           //无须自定义链接指针，已由挂钩实现
    point(int a = 0, int b = 0) :
        x(a), y(b) {}
};

使用方式如下：

point p1, p2(2, 2), p3(3, 3);   //三个节点对象，未连接
slist<point> sl;                //声明一个单链表侵入式容器，可容纳point

sl.push_front(p1);              //缺省情况下不能使用push_back()
sl.push_front(p2);
sl.push_front(p3);              //p3->p2->p1

assert(sl.size() == 3);
sl.reverse();                   //逆序算法，p1->p2->p3

for (auto& p : sl)
{
    std::cout << p.x << "-" << p.y << " ";
}

sl.erase(boost::next(sl.begin()));  //删除链表中的第二个节点

要想使用push_back()，要在slist的模板参数中增加一个配置选项cache_last<true>。

slist<point,cache_last<true> > sl;
sl.push_back(p1);

2.使用成员挂钩

point类修改成使用成员挂钩的形式：

class point
{
public:
    int x, y;                           //无须自定义链接指针，已由挂钩实现
    slist_member_hook<> m_hook;         //成员挂钩，缺省配置
    point(int a = 0, int b = 0) :
        x(a), y(b) {}
};

使用成员挂钩的类，在侵入式容器容纳时，需要用一个元函数member_hook作为配置选项，告诉容器成员挂钩的类型和挂钩变量名：

slist<point,                                //元素类型
    member_hook<point,                      //成员挂钩选项
    slist_member_hook<>, &point::m_hook>    //成员挂钩变量
> sl;

完整使用：

#include <boost/next_prior.hpp>
#include <boost/intrusive/slist.hpp>
#include <boost/ptr_container/ptr_vector.hpp>
#include <boost/assign/ptr_list_of.hpp>
#include <boost/foreach.hpp>
using namespace boost;
using namespace boost::assign;
using namespace boost::intrusive;

int main()
{
    point p1, p2(2, 2), p3(3, 3);           //三个节点对象，未连接            

    ptr_vector<point> vec = ptr_list_of<point>()(2, 2)(3, 3);

    typedef member_hook<point, slist_member_hook<>, &point::m_hook> member_option;

    slist<point, member_option> sl;

    BOOST_REVERSE_FOREACH(auto& p, vec)
    {
        sl.push_front(p);
    }
    assert(sl.size() == 3);

    for (point& p : sl)
    {
        std::cout << p.x << "-" << p.y << " ";
    }

    return 0;
}

这里，我们先声明了指针容器并先插入元素到指针容器中，后进行侵入式容器的创建，如果两者的声明顺序调换，则会导致在函数结束时指针容器vec和里面的元素先被销毁，侵入式容器后销毁时会因为访问不存在的元素而抛出异常。
如果要避免这个错误，也可以在程序结束之前调用侵入式容器的成员函数clear()，提前清空，实际上它并不是删除元素，只是把元素间的链接关系断开。
或者通过改变挂钩和侵入式容器的配置选项，允许元素在析构时自动从容器中断开连接：

class point
{
public:
    int x, y;                           //无须自定义链接指针，已由挂钩实现
    slist_member_hook<link_mode<auto_unlink>> m_hook;           //成员挂钩，缺省配置
    point(int a = 0, int b = 0) :
        x(a), y(b) {}
};

typedef member_hook<point, slist_member_hook<link_mode<auto_unlink>>, &point::m_hook> member_option;

//自动断开连接功能需禁用常量时间的size()功能
slist<point,member_option,constant_time_size<false> > sl;

---

intrusive库里的概念

1.节点

节点，是抽象了手工实现链表时的链接指针和其他信息，把它们封装为一个类：单链表提供一个指针（后继），双向链表提供两个指针（前驱和后继），树结构提供三个指针（父指针和左右指针）以及颜色、平衡等其他信息。
有了节点的概念，用户可以直接以继承或者成员的方式复用而无须自行编写侵入代码。

template<class VoidPointer>
struct slist_node
{
    typedef typename pointer_rebind<                //元函数计算
        VoidPointer, slist_node>::type node_ptr;    //单链表节点指针类型
    node_ptr next_;                                 //单链表节点指针
};

pointer_rebind模仿C++11/14的元函数pointer_traits来定义节点指针类型，所以节点不仅可以使用原始指针，也可以使用智能指针。

2.节点特征

节点特征是一个traits类，封装了操作节点的基本方法，对外提供一致抽象接口。不同的节点特征有不同的接口，但通常都提供节点类型、节点指针类型、取节点前驱后继（静态成员函数）等操作。

template<class VoidPointer>
struct slist_node_traits
{
    typedef some_define node;
    typedef some_define node_ptr;
    typedef some_define const_node_ptr;

    static node_ptr get_next(const_node_ptr& n);
    static void     set_next(node_ptr n, node_ptr next);
};

3.节点算法

节点算法抽象了链式数据结构的算法，使用节点特征类来操作节点，以静态成员函数的形式提供链表的一些基本操作：初始化、连接节点、断开连接节点等。
节点算法与配套的节点特征类必须是接口兼容的，否则会在编译期发生错误。
例如单链表slist的循环节点算法：

template<class NodeTraits>
class circular_slist_algorithms
{
public:
    typedef NodeTraits::node            node;
    typedef NodeTraits::node_ptr        node_ptr;
    typedef NodeTraits::const_node_ptr  const_node_ptr;
    typedef NodeTraits                  node_traits;

    static void         init();         //初始化操作
    static bool         inited();       //是否已经初始化
    static void         unlink_after(); //断开连接
    static void         link_after();   //连接
    static void         link_header();  //初始化头节点
    static std::size_t  count();        //计算节点数量
};

使用节点算法可以避免直接操作节点，在更高抽象层次上实现数据结构。

typedef slist_node<void*>                           node_t;
typedef slist_node_traits<void*>                    node_traits_t;
typedef circular_slist_algorithms<node_traits_t>    algo;

node_t n1, n2;

algo::init_header(&n1);
assert(algo::count(&n1) == 1);

algo::link_after(&n1, &n2);             //连接n1和n2
assert(algo::count(&n1) == 2);

algo::unlink(&n1);                      //断开n1的连接
assert(algo::count(&n2) == 1);

4.值特征

值特征类似非侵入式容器中值类型T的概念，把用户自有的值类型与节点、节点特征封装在一起，可以提供给节点算法使用。
值特征类通常具有下面的形式：

struct value_traits
{
    typedef some_define node_traits;    //节点特征类
    typedef some_define value_type;     //值类型
    typedef some_define node_ptr;       //节点指针类型
    typedef some_define pointer;        //指向值的指针类型

    static const linik_mode_type link_mode = some_link_mode;    //链接策略

    static node_ptr to_node_ptr(value_type &value);     //指针转换
    static pointer  to_value_ptr(node_ptr n);           //指针转换
};

值特征类中，链接模式link_mode是一个枚举值，用于确定侵入式容器的链接处理策略，有以下三个取值：

• safe_link：节点在插入删除时会检查指针，可以安全地插入，是最常用的策略
• auto_unlink：可以在节点对象析构时自动从容器中移除，虽然方便但安全性有所降低，只能用于非常量时间的容器。
• normal_link：节点在进行插入删除操作时不做任何检查。

5.挂钩

前面示例过挂钩的使用，它实际上包含了节点、节点算法和其他一些信息。generic_hook是所有侵入式容器通用的挂钩类，它使用了模板元编程来计算类型，元函数detail::if_c用参数Tag决定挂钩的节点类型。如果是成员挂钩，那么直接使用节点算法里的节点类型，如果是基类挂钩，则计算得到一个包装类型node_holder<…>。

6.选项

选项是intrusive库中用于配置、调整侵入式容器行为的一大族高阶元数据，如link_mode、optimize_size、cache_last等。
选项元数据的定义在<boost/intrusive/options.hpp>，通常形式是：

template<class OptionName>
struct option_name
{
    template<class Base>
    struct pack :Base
    {
        typedef OptionName option_name;
    };
};

元数据option_name内部的元函数是pack，它会把参数OptionName定义为一个与元数据同名的类型（即option_name）。这里使用了pack而不是常用的apply，因为后续这些高阶元数据要配合另一个元函数pack_options来执行元数据打包的操作。

template<class Prev,class Next>
struct do_pack      //子元函数，调用高阶元数据的pack元函数
{
    typedef typename Next::template pack<Prev> type;
};

template<class DefaultOptions,class O1,class O2>
struct pack_options
{
    typedef
        typename do_pack
        <typename do_pack
        <DefaultOptions, O1>::type  //对O1打包
        , O2                            //对O2打包
        >::type type;
};

不是很理解这个是干啥

7.处置器

由于侵入式容器不做内存管理，不能销毁元素，所以intrusive库提出了处置器的概念帮助侵入式容器“销毁”元素。
处置器是一个函数对象，它可以用某种策略处理元素指针，如：

struct Disposer
{
    void operator()(T* to_dispose)  //operator()接受指针
    {...}                           //处置指针，通常是delete to_dispose来销毁对象
};

侵入式容器的pop_back()、clear()、erase()等涉及容器内元素移除的操作都有两个版本，第一个与标准容器接口相同，简单地断开元素在容器中的链接，元素没有真正销毁，第二个是带”_and_dispose”后缀的函数，除了标准参数外还多出一个处置器参数，侵入式容器使用它来处置对象。

8.克隆

侵入式容器和指针容器一样，提供了克隆的概念。
所有的侵入式容器都提供一个clone_from()成员函数，实现克隆操作，基本形式是：

template<class Cloner,class Disposer>
void clone_from(const Cont &src,Cloner c,Disposer d);

两个模板参数分别是克隆器和处置器，容器先使用处置器d清除内部的所哟元素，然后使用克隆器c从src逐个克隆元素到本容器，如果克隆过程发生异常调用处置器d清除已经克隆的元素。
克隆器也是一个函数对象：

struct Cloner
{
    template<typename ValueType>
    ValueType* operator()(const ValueType& r);
};

---

链表

intrusive库提供两种链表式侵入式容器：slist和list。
slist是单链表，只有一个指针的空间开销，时间复杂度较高。
list是双向链表，使用两个指针，类似std::list，其用法更灵活。

节点和算法

list使用的节点是list_node，它提供了前驱和后继两个指针：

template<class VoidPointer>
struct list_node
{
    typedef typename pointer_rebind<
        VoidPointer, list_node>::type   node_ptr;   //指针类型定义
    node_ptr                            next_;      //前驱指针
    node_ptr                            prev_;      //后继指针
};

list_node对应的节点特征类是list_node_traits，封装对list_node的所有操作：

template<class VoidPointer>
struct list_node_traits
{
    typedef list_node<VoidPointer>  node;
    typedef some_define             node_ptr;
    typedef some_define             const_node_ptr;

    static node_ptr                 get_previous(const_node_ptr n);
    static void                     set_previous(node_ptr n, node_ptr prev);
    static node_ptr                 get_next(const_node_ptr n);
    static void                     set_next(node_ptr n, node_ptr next);
};

list使用的节点算法是circular_list_algorithms，接口与circular_slist_algorithms类似。

基类挂钩

list使用的基类挂钩是list_base_hook，派生自generic_hook，实际上是工厂元函数make_list_base_hook的计算结果。

template<class O1,class O2,class O3>
class list_base_hook
    :public make_list_base_hook<O1, O2, O3>::type
{
    void swap_nodes(list_base_hook &);
    bool is_linked() const;             //挂钩是否已经连接
    void unlink();                      //断开挂钩连接，要求链接模式为auto_unlink
};

template<class O1 = none, class O2 = none, class O3 = none>
struct make_list_base_hook
{
    typedef typename pack_options           //选项元数据打包
        <hook_defaults,                     //使用缺省挂钩参数
        O1, O2, O3>::type packed_options;

    typedef generic_hook                    //使用挂钩基类
        <circular_list_algorithms<...>      //使用circular_list_algorithms
        , typename packed_options::tag      //标签
        , packed_options::link_mode         //链接模式
        , ListBaseHookId                    //链表基类挂钩枚举值
        > implementation_defined;

    typedef implementation_defined type;    //返回元函数的计算结果
};

一个完整定义的链表基类挂钩是这样的：

list_base_hook<
    tag<struct some_tag>,   //使用一个“不完整类型”定义标签
    void_pointer<void*>,    //指针通常都使用void*定义
    link_mode<safe_link> >  //链表模式使用safe_link

因为使用了元素据打包，所以对三个选项顺序无要求：

• tag：一个语法层面的标签，用于区分不同类别的挂钩。不同的类可以使用相同的标签，但同一个类如果使用多个基类挂钩则标签不能相同，默认值为default_tag。
• void_pointer：挂钩使用的指针类型，默认值是void*
• link_mode：挂钩的链接模式，默认值是safe_link

成员挂钩

list使用的成员挂钩是list_member_hook，是由另一个工厂元函数make_list_member_hook产生的，与make_list_base_hook仅有微小的不同。

template<class O1,class O2,class O3>
class list_member_hook
    :public make_list_member_hook<O1, O2, O3>::type
{...};      //接口同list_base_hook

template<class O1 = none, class O2 = none, class O3 = none>
struct make_list_member_hook
{
    typedef typename pack_options           //选项元数据打包
        <hook_defaults,                     //使用缺省挂钩参数
        O1, O2, O3>::type packed_options;

    typedef generic_hook                    //使用挂钩基类
        <circular_list_algorithms<...>      //使用circular_list_algorithms
        , member_tag                        //注意这里是成员标签
        , packed_options::link_mode         //链接模式
        , NoBaseHookId                      //成员（非基类）挂钩类型
        > implementation_defined;

    typedef implementation_defined type;    //返回元函数的计算结果
};

只有在挂钩类别上与list_base_hook不同，模板参数和成员函数均相同。

基本用法

class point :public list_base_hook<>
{
public:
    int x, y;
    point(int a = 0, int b = 0) :
        x(a), y(b) {}

    friend bool operator==(const point& l, const point& r)
    {
        return l.x == r.x && l.y == r.y;
    }
    friend bool operator<(const point& l, const point& r)
    {
        return l.x < r.x;
    }
};

int main()
{
    using namespace boost::assign;
    ptr_vector<point> vec = ptr_list_of<point>(0)(1)(2)(3)(4);

    typedef make_list<point>::type list_t;
    list_t lt;
    assert(lt.empty());

    lt.push_back(vec[2]);       //向末端添加元素，链表：2
    lt.push_front(vec[3]);      //向前端添加元素，链表：3->2

    assert(!lt.empty() && lt.size() == 2);
    assert(lt.front().x == 3);
    assert(lt.back().x == 2);

    lt.insert(boost::next(lt.begin()), vec.begin(), vec.begin() + 2);   //3->0->1->2
    for (auto& p : lt)
    {
        std::cout << p.x << ",";
    }

    lt.reverse();           //2->1->0->3
    lt.pop_front();         //1->0->3

    lt.insert(boost::prior(lt.end()), vec[4]);      //1->0->4->3
    for (auto& p : lt)
    {
        std::cout << p.x << ",";
    }
    lt.sort();              //0->1->3->4

    lt.erase(boost::prior(lt.end(), 2));    //0->1->4

    return 0;
}

基类挂钩使用自定义标签时需要明确写出挂钩类型，因为此时无法自动推倒出基类挂钩类型。

class point:public list_base_hook<tag<struct a_tag> >{};
typedef make_list<point,
    base_hook<list_base_hook<tag<a_tag>>> >::type list_t;

成员挂钩的用法和基类挂钩没有太大差别，只是需要在list的模板参数列表中配置member_hook选项，写法上麻烦：

class point
{
public:
    ...
    list_member_hook m_hook;
};
typedef make_list<point,
    member_hook<point,    //成员挂钩选项
    list_member_hook<>,&point::m_hook>>::type list_t;

特有用法

左右移动
成员函数shift_backwards()和shift_forward()相当于std::rotate算法，令链表中的元素循环后移或前移，默认移动一个元素。

using namespace boost::assign;
ptr_vector<point> vec = ptr_list_of<point>(0)(1)(2)(3)(4);

typedef make_list<point>::type list_t;
list_t lt(vec.begin(), vec.end());
assert(lt.size() == 5);     //链表：0->1->2->3->4

lt.shift_backwards(2);      //循环后移两个元素，链表3->4->0->1->2
lt.shift_forward();         //循环前移一个元素，链表4->0->1->2->3

处置器相关操作
大部分涉及容器内元素移除的操作，都有对应的使用处置器的版本，大部分函数都是操作完毕后使用处置器的operator()处理移除的元素，只有dispose_and_assign()是先使用处置器然后再赋值。
示例定义一个简单的处置器函数对象，输出处置的值然后删除它：

struct disposer
{
    void operator()(point* p)
    {
        std::cout << "dispose:" << p->x << std::endl;
        checked_delete(p);
    }
};

int main()
{
    using namespace boost::assign;
    ptr_vector<point> vec = ptr_list_of<point>(0,0)(1,1)(2,2)(3,3)(4,4);

    typedef make_list<point>::type list_t;
    list_t lt(vec.begin(), vec.end());

    disposer d;

    lt.pop_front_and_dispose(d);
    lt.erase_and_dispose(boost::next(lt.begin()), d);
    lt.remove_and_dispose(point(4, 4), d);

    lt.push_back(*(new point(3, 3)));
    lt.unique_and_dispose(d);

    return 0;
}

克隆
成员函数clone_from()从另一个容器中克隆元素到本容器内，要求元素必须有克隆器和处置器两个函数对象。

struct cloner
{
    template<typename T>
    T* operator()(const T& r)
    {
        return factory<T*>()(r);
    }
};

//使用
using namespace boost::assign;
ptr_vector<point> vec = ptr_list_of<point>(0,0)(1,1)(2,2)(3,3)(4,4);

typedef make_list<point>::type list_t;
list_t lt(vec.begin(), vec.end());

list_t lt2;
assert(lt2.empty());

lt2.clone_from(lt, cloner(), disposer());
assert(lt2 == lt);

迭代器特殊操作
侵入式容器修改了元素的代码，所有的元素都含有链接信息，所以侵入式容器可以直接从一个值获得对应的迭代器。
这个功能要求元素必须已经被容器链接上，即挂钩的is_linked()返回true，否则会引起断言异常。
所有的侵入式容器都提供成员函数iterator_to()，可以返回元素对应的迭代器位置，多数还有一个同等功能的静态成员函数s_iterator_to()。
container_from_end_iterator()还可以从逾尾迭代器获得侵入式容器的引用。

using namespace boost::assign;
ptr_vector<point> vec = ptr_list_of<point>(0, 0)(1, 1)(2, 2)(3, 3)(4, 4);

typedef make_list<point>::type list_t;
list_t lt;

lt.push_back(vec[1]);
lt.push_back(vec[3]);

assert(vec[1].is_linked());
assert(lt.iterator_to(vec[1]) == lt.begin());

assert(vec[3].is_linked());
assert(list_t::s_iterator_to(vec[3]) == boost::prior(lt.end()));

list_t& rlt = list_t::container_from_end_iterator(lt.end());
assert(addressof(rlt) == addressof(lt));

---

有序集合

intrusive库基于红黑树、AVL树、splay树、scapegoat树、二叉树和堆实现了五种侵入式有序集合容器，这些容器除了内部使用的算法不同，接口基本相同，类似标准集合容器。

节点和算法

set基于红黑书实现，使用的节点类名称是rbtree_node，有两个实现类，使用optimize_size选项决定优化策略，紧凑版本可以节省一个整数的空间。

template<class VoidPointer>
struct compact_rbtree_node      //紧凑版本
{
    typedef pointer_rebind<VoidPointer, node>::type node_ptr;
    enum color{red_t,black_t};          //颜色枚举
    node_ptr parent_, left_, right_;    //父指针和左右指针
};

struct rbtree_node              //普通版本
{
    ...
    color color_;               //多出颜色变量
};

节点特征类rbtree_node_traits使用一个bool类型模板参数OptimizeSize定制，它再使用元函数rbtree_node_traits_dispatch特化到具体的实现类default_rbtree_node_traits_impl或者compact_rbtree_node_traits_impl。
set使用的算法是rbtree_algorithms。

基类挂钩

set使用的基类挂钩是set_base_hook，同样使用了工厂元函数make_set_base_hook。

template<class O1,class O2,class O3,class O4>
class set_base_hook
    :public make_set_base_hook<O1, O2, O3, O4>::type
{...};      //成员同list_base_hook

template<class O1, class O2, class O3, class O4>
struct make_set_base_hook
{
    typedef generic_hook                //使用挂钩基类
        <rbtree_algorithms<...>         //使用rbtree_algorithms
        , typename packed_options::tag  //标签
        , packed_options::link_mode     //链接模式
        , RbTreeBaseHookId              //红黑树基类挂钩枚举值
        > implementation_defined;
};

set_base_hook使用四个选项：tag、void_pointer、link_mode、optimize_size，前三个同list_base_hook，第四个取true或false来决定set是否优化空间。

成员挂钩

template<class O1,class O2,class O3,class O4>
class set_member_hook
    :public make_set_member_hook<O1, O2, O3, O4>::type
{};

template<class O1, class O2, class O3, class O4>
struct make_set_member_hook
{
    typedef generic_hook                //使用挂钩基类
        <rbtree_algorithms<...>         //使用rbtree_algorithms
        , member_tag                    //成员标签
        , packed_options::link_mode     //链接模式
        , NoBaseHookId                  //成员挂钩枚举值
        > implementation_defined;
};

同样只有在挂钩类别上与set_base_hook不同，模板参数和成员函数均相同

基本用法

class point :public set_base_hook<>,    //set基类挂钩
    boost::less_than_comparable<point>
{
public:
    int x, y;
    point(int a = 0, int b = 0) :
        x(a), y(b) {}

    friend bool operator==(const point& l, const point& r)
    {
        return l.x == r.x && l.y == r.y;
    }
    friend bool operator<(const point& l, const point& r)
    {
        return l.x < r.x;
    }
};

int main()
{
    using namespace boost::assign;
    ptr_vector<point> vec = ptr_list_of<point>(0,0)(1,1)(2,2)(3,3)(4,4);

    typedef make_set<point>::type set_t;
    set_t s;
    assert(s.empty());

    assert(s.insert(vec[0]).second);
    assert(s.insert(vec[2]).second);
    assert(!s.insert(vec[2]).second);   //不允许重复插入

    assert(s.size() == 2);
    assert(s.count(point()) == 1);

    s.insert(vec.begin(), vec.end());
    assert(s.size() == 5);

    s.erase(s.lower_bound(2), s.upper_bound(2));

    return 0;
}

特有用法

set具有与list相同的一些侵入式容器特有的接口，包括克隆、处置器、迭代器的特殊操作，不一样的是，set无须使用逾尾迭代器就可以从迭代器获得容器的引用。

using namespace boost::assign;
ptr_vector<point> vec = ptr_list_of<point>(0, 0)(1, 1)(2, 2)(3, 3)(4, 4);

typedef make_set<point>::type set_t;
set_t s(vec.begin(), vec.end());

s.erase_and_dispose(s.begin(), boost::next(s.begin(), 2), disposer());

set_t s2;
s2.clone_from(s, cloner(), disposer());
assert(s2.begin()->x == 2);
assert(s2 == s);

assert(addressof(s2) == addressof(s2.container_from_iterator(boost::next(s2.begin())));

使用键操作值
有时候容器内存储的值类型的构造成本很高，为了避免临时对象的开销，set允许使用一个函数对象KeyValueCompare比较容器中元素是否与一个低成本的键KeyType相同，从而提高了运行效率。
函数对象KeyValueCompare是一个不等关系比较，它与集合容器compare选项配置的排序准则谓词一致，简单地说，同为小于关系或者同为大于关系。

struct key_compare
{
    typedef const int&      key_type;   //键类型
    typedef const point&    value_type; //值类型

    //因为要比较不同类型，所以需要两个operator()
    bool operator()(key_type k,value_type p) const
    {
        return k < p.x;
    }
    bool operator()(value_type p,key_type k) const
    {
        return p.x < k;
    }
};

int main()
{
    using namespace boost::assign;
    ptr_vector<point> vec = ptr_list_of<point>(0,0)(1,1)(2,2)(3,3)(4,4);

    typedef make_set<point>::type set_t;    //使用缺省的std::less<>
    set_t s(vec.begin(), vec.end());

    key_compare kc;                         //一个键比较函数对象

    assert(s.count(1, kc) == 1);            //使用键计算元素数量
    assert(s.find(2, kc)->x == 2);          //使用键查找元素
    assert(s.find(9, kc) == s.end());

    assert(s.erase(3,key_compare()) == 1);  //使用键删除元素
    assert(s.find(point(3, 3)) == s.end()); //构造值对象查找，开销大

    return 0;
}

检查插入
set使用键操作为插入提供了类似数据库的check-commit机制，可以用在值类型的构造成本很高的场合。
insert_check()函数使用KeyValueCompare比较容器中的元素是否与KeyType相等，避免构造大对象的开销，如果允许插入，那么紧接着调用insert_commit()来完成插入操作。

using namespace boost::assign;
ptr_vector<point> vec = ptr_list_of<point>(0, 0)(1, 1)(2, 2)(3, 3)(4, 4);

typedef make_set<point>::type set_t;    //使用缺省的std::less<>
set_t s(vec.begin(), boost::next(vec.begin(), 3));

set_t::insert_commit_data idata;        //一个用于提交的数据类型

                                        //比较键0，已经存在，无法插入
assert(!s.insert_check(0, key_compare(), idata).second);

assert(s.insert_check(4, key_compare(), idata).second);
s.insert_commit(vec[4], idata);

assert(s.find(4, key_compare()) != s.end());

---

无序集合

unorderd_set和unordered_multiset是无序集合容器，不是使用指针链接而是使用散列表来实现元素的查找与存储，两者功能基本相同。

节点与算法

无序集合容器使用的节点类是unordered_node，基于单链表节点slist_node实现，并用bool类型模板参数进行了特化。

template<class VoidPointer,bool StoreHash,bool OptimizeMultiKey>
struct unordered_node :public slist_node<VoidPointer>
{
    typedef some_define node_ptr;
    node_ptr            prev_in_group_; //根据OptimizeMultiKey选项可被优化
    std::size_t         hash_;          //根据StoreHash选项可被优化
};

无序集合容器的节点特征类是unordered_node_traits，基于单链表特征类，增加了操作散列值的成员函数。

template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
struct unordered_node_traits :public slist_node_traits<VoidPointer>
{
    static std::size_t  get_hash(const_node_ptr n);
    static void         set_hash(node_ptr n, std::size_t n);
};

无序集合容器使用的算法是unordered_algorithms，基于circular_slist_algorithms。

基类挂钩

无序集合容器使用的基类挂钩是unordered_set_base_hook，同样使用了工厂元函数make_unordered_set_base_hook。

template<class O1,class O2,class O3,class O4>
class unordered_set_base_hook
    :public make_unordered_set_base_hook<O1,O2,O3,O4>::type
{};     //成员同list_base_hook

template<class O1, class O2, class O3, class O4>
struct make_unordered_set_base_hook
{
    typedef generic_hook                //使用挂钩基类
        <get_uset_node_algo<...>        //使用unordered_algorithms
        , typename packed_options::tag  //标签
        , packed_options::link_mode     //链接模式
        , HashBaseHookId                //有序集合基类挂钩枚举值
        > implementation_defined;
};

unordered_set_base_hook可以使用五个选项：tag、void_pointer、link_mode、store_hash和optimize_multikey，前三个同list_base_hook。后两个：
store_hash：挂钩中保存散列值，重散列时无须重新计算，可以提高性能，缺省值为false
optimize_multikey：unordered_multiset专用选项，挂钩中存储指针，可以把相等的元素聚集在一起提高性能，缺省为false。

成员挂钩

template<class O1,class O2,class O3,class O4>
class unordered_set_member_hook
    :public make_unordered_set_member_hook<O1,O2,O3,O4>::type
{};     //成员同list_base_hook

template<class O1, class O2, class O3, class O4>
struct make_unordered_set_member_hook
{
    typedef generic_hook                //使用挂钩基类
        <get_uset_node_algo<...>        //使用unordered_algorithms
        , member_tag                    //成员挂钩标签
        , packed_options::link_mode     //链接模式
        , NoBaseHookId                  //成员挂钩枚举值
        > implementation_defined;
};

基本用法

unordered_set属于半侵入式容器，故它的用法与纯侵入式有所不同——需要在外部额外分配一个辅助内存空间来维护散列容器所需的负载因子。
辅助内存空间是一个unordered_set::bucket_type类型的桶数组，每一个无序容器必须使用专用的桶数组，生命周期必须长于unordered_set，也就是说必须在unordered_set销毁后才能销毁桶数组。
unordered_set的构造函数需要使用unordered_set::bucket_traits包装bucket_type数组，以使其作为参数初始化：

typedef make_unordered_set<point>::type set_t;
set_t::bucket_type buckets[20];
set_t s(set_t::bucket_traits(buckets, 20)); //构造一个空容器

也可以用动态数组

std::vector<set_t::bucket_type> buckets(20);
set_t s(set_t::bucket_traits(&buckets[0], 20)); //构造一个空容器

桶一旦被指定就不能变动，除非使用rehash()传入一个新的桶数组重散列。

class point :public unordered_set_base_hook<>   //基类挂钩
{
public:
    int x, y;
    point(int a = 0, int b = 0) :
        x(a), y(b) {}

    friend bool operator==(const point& l, const point& r)
    {
        return l.x == r.x && l.y == r.y;
    }
    friend std::size_t hash_value(const point& p)       //散列函数
    {
        size_t seed = 2016;
        hash_combine(seed, p.x);
        hash_combine(seed, p.y);
        return seed;
    }
};

int main()
{
    using namespace boost::assign;
    ptr_vector<point> vec = ptr_list_of<point>(0,0)(1,1)(2,2)(3,3)(4,4);

    typedef make_unordered_set<point>::type set_t;
    std::vector<set_t::bucket_type> buckets(2);     //一个很小的辅助空间
    set_t s(vec.begin(), vec.end(),set_t::bucket_traits(&buckets[0],2));

    assert(s.size() == 5);
    assert(s.count(point(1, 1)) == 1);

    for (auto& p : s)               //无序容器只能正向遍历，无逆向遍历
    {
        std::cout << p.x << ",";
    }

    s.erase(s.find(point(1, 1));

    set_t::bucket_type buckets2[10];
    s.rehash(set_t::bucket_traits(buckets2, 10));

    s.clear();

    return 0;
}

unordered_set的特有用法

unordered_set具有与set相同的一些侵入式容器特有的接口，包括克隆、处置器、迭代器的特殊操作，但稍有不同：

• 没有container_from_end_iterator()和container_from_iterator()
• 没有静态成员函数s_iterator_to()
• 不能执行容器比较操作

using namespace boost::assign;
ptr_vector<point> vec = ptr_list_of<point>(0, 0)(1, 1)(2, 2)(3, 3)(4, 4);

typedef make_unordered_set<point>::type set_t;
std::vector<set_t::bucket_type> buckets(5);     //一个很小的辅助空间
set_t s(vec.begin(), vec.end(), set_t::bucket_traits(&buckets[0], 5));

s.erase_and_dispose(s.begin(), boost::next(s.begin(), 2), disposer());

set_t::bucket_type buckets2[10];
set_t s2(set_t::bucket_traits(buckets2, 10));
s2.clone_from(s, cloner(), disposer());

assert(*s2.begin() == *s.begin());

使用键操作值
unordered_set也可以使用键操作值，但由于是无序，所以不使用比较函数对象，而是使用KeyHasher和KeyValueEqual，这两个函数对象分别对应equal和hash，差别仅在于是对键操作，结果应与对值操作一致。

typedef std::pair<int, int> ukey_type;          //使用一个pair作为键
struct key_hasher                               //散列函数对象
{
    std::size_t operator()(const ukey_type& k)  //算法应与point一致
    {
        size_t seed = 2016;
        hash_combine(seed, k.first);
        hash_combine(seed, k.second);
        return seed;
    }
};

struct key_equal
{
    bool operator()(const ukey_type& k, const point& p)
    {
        return k.first == p.x&&k.second == p.y;
    }
    bool operator(const point& p,const ukey_type& k)
    {
        return operator()(k, p);
    }
};


int main()
{
    using namespace boost::assign;
    ptr_vector<point> vec = ptr_list_of<point>(0,0)(1,1)(2,2)(3,3)(4,4);

    point tmp(5, 5);                //必须在侵入式容器之前声明，否则会产生运行时错误。

    typedef make_unordered_set<point>::type set_t;
    std::vector<set_t::bucket_type> buckets(5);     //一个很小的辅助空间
    set_t s(vec.begin(), vec.end(),set_t::bucket_traits(&buckets[0],5));

    key_hasher kh;
    key_equal keq;

    assert(s.count(make_pair(1, 1), kh, keq) == 1);
    assert(s.find(make_pair(2, 2), kh, keq) != s.end());

    set_t::insert_commit_data idata;        //用于提交的数据类型

    assert(s.insert_check(make_pair(5, 5), kh, keq, idata).second);
    s.insert_commit(tmp, idata);
    assert(s.find(make_pair(5, 5), kh, keq) != s.end());

    return 0;
}

---

其他

链接模式

前面提过，挂钩的连接模式(link mode)有三种策略：safe_link、auto_unlink和normal_link。
safe_link作为最常用的一种链接模式，可以使挂钩安全地处理链接。挂钩在构造时是未连接状态，析构时检查挂钩的连接状态，如果已连接则产生断言异常，从而保证侵入式容器不会发生访问无效指针的错误。在插入容器时，safe_link的挂钩也会检查连接状态，不允许重复插入同一个容器，移出容器会自动把节点置为未连接状态，因此safe_link如其名，是安全的。

auto_unlink的大部分行为都和safe_link相同，但是在析构时会自动调用算法的unlink()函数从容器中自我移除。同时auto_link还为节点提供了可用的unlink()成员函数，用户可以在容器外任意地把节点移出侵入式容器，这可能导致容器内容在未经过容器操作的情况下发生了改变，多线程时没有安全保证。auto_unlink不能使用常量时间的获取大小操作，也就是说必须在容器的模板参数中明确配置选项constant_time_size<false>。

normal_link是一个完全无任何操作的”空模式“，在节点的构造、析构、插入、移除时都不做任何检查，适用于手工管理节点的情况。

同时使用多个挂钩

侵入式容器不拷贝对象，不分配内存，仅仅把已有的对象链接在一起，因此，如果对象含有多个挂钩，那么就可以同时被多个（挂钩对应的）侵入式容器容纳，相当于给这些对象建立多个不同索引方式的视图。

class point :
    public list_base_hook<>,                            //链表基类挂钩，缺省标签
    public unordered_set_base_hook<tag<struct us_tag>>  //无序集合基类挂钩
{
public:
    int x, y;
    point(int a = 0, int b = 0) :
        x(a), y(b) {}

    set_member_hook<>   m_shook;        //用于有序单键集合的成员挂钩
    set_member_hook<>   m_mshook;       //用于有序多键集合的成员挂钩

    friend bool operator==(const point& l, const point& r)
    {
        return l.x == r.x && l.y == r.y;
    }
    friend std::size_t hash_value(const point& p)       //散列函数
    {
        size_t seed = 2016;
        hash_combine(seed, p.x);
        hash_combine(seed, p.y);
        return seed;
    }
};

int main()
{
    using namespace boost::assign;
    ptr_vector<point> vec = ptr_list_of<point>(0)(1)(2)(3)(4)(3)(2);

    typedef make_list<point>::type list_t;          //链表容器

    typedef make_unordered_set<point,
        base_hook<unordered_set_base_hook<tag<us_tag>>> >::type uset_t;     //无序集合容器

    typedef make_set<point,
        member_hook<point, set_member_hook<>, &point::m_shook>>::type set_t;//有序单键集合容器

    typedef make_multiset<point,
        member_hook<point, set_member_hook<>, &point::m_mshook>>::type mset_t;//有序多键集合容器

    list_t lt(vec.rbegin(), vec.rend());            //逆序插入链表
    for (auto& p : lt)
    {
        std::cout << p.x << ",";
    }

    set_t s(lt.begin(), lt.end());
    mset_t ms(lt.begin(), lt.end());
    assert(s.size() == 5 && ms.size() == 7);

    uset_t::bucket_type buckets[20];
    uset_t us(uset_t::bucket_traits(buckets,20));

    us.insert(vec.begin(), vec.end());

    lt.pop_front();
    assert(lt.size() == 6 && 
        s.size() == 5 && ms.size() == 7);   //其他容器不受影响

    set_t::iterator iter = set_t::s_iterator_to(*us.begin());

    return 0;
}

万能挂钩

同时使用多个挂钩是一个很有用的功能，但需要为被侵入类编写不同容器对应的挂钩代码，而intrusive库在<boost/intrusive/any_hook.hpp>提供了可用于任意侵入式容器的万能挂钩——any_base_hook和any_member_hook。【但不能使用auto_unlink链接模式】

class point :
    public any_base_hook<>
{
public:
    int x, y;
    point(int a = 0, int b = 0) :
        x(a), y(b) {}

    any_member_hook<>   m_shook;        //用于有序单键集合的成员挂钩
    any_member_hook<>   m_mshook;       //用于有序多键集合的成员挂钩

    friend bool operator==(const point& l, const point& r)
    {
        return l.x == r.x && l.y == r.y;
    }
};

配置容器时需要使用辅助元数据any_to_xxx_hook，把any_hook转换成特定容器所需的挂钩选项。

typedef any_to_list_hook<base_hook<any_base_hook<>>> list_hook_opt;
typedef make_list<point, list_hook_opt>::type list_t;           //链表容器

typedef any_to_set_hook<member_hook<point, any_member_hook<>, &point::m_shook>> set_hook_opt;
typedef make_set<point,set_hook_opt>::type set_t;               //有序单键集合容器

typedef any_to_set_hook<member_hook<point, any_member_hook<>, &point::m_mshook>> mset_hook_opt;
typedef make_multiset<point, mset_hook_opt>::type mset_t;       //有序多键集合容器