Subscribed unsubscribe Subscribe Subscribe

Boost.Intrusive のコンテナを hook なしで使う

boost intrusive c++

Boost.Intrusive を使いたい場面は結構あるものの、なんだ hook とか書かなくちゃいけないのか、既存のデータ構造には適用できないのか、と諦めていた。ところが、よくよくソースを読んでみると ValueTraits という trait クラスを指定することで完全にノードの形式をカスタマイズできるようだったので、試してみた。つか、書いてみて分かったけどリファレンスにさりげなく載ってた。なんだよこれ。

#define BOOST_TEST_MODULE "list"

#include <boost/intrusive/list.hpp>
#include <boost/test/included/unit_test.hpp>
#include <iostream>

class my_list_node
{
public:
    my_list_node(int v = 0): v_(v) {}

    bool operator<(my_list_node const& that) const {
        return v_ < that.v_;
    }

    operator int() const {
        return v_;
    }

public:
    my_list_node* next;
    my_list_node* prev;

private:
    int v_; 
};

struct my_list_value_traits
{
    typedef my_list_node      value_type;
    typedef value_type*       pointer;
    typedef value_type const* const_pointer;
    typedef value_type&       reference;
    typedef value_type const& const_reference;

    struct node_traits
    {
        typedef my_list_node node;
        typedef my_list_node* node_ptr;
        typedef my_list_node const* const_node_ptr;

        static node_ptr get_previous(const_node_ptr n)
        {
            return n->prev;
        }

        static node_ptr get_next(const_node_ptr n)
        {
            return n->next;
        }

        static void set_previous(node_ptr n, node_ptr v)
        {
            n->prev = v;
        }

        static void set_next(node_ptr n, node_ptr v)
        {
            n->next = v;
        }
    };

    typedef node_traits::node           node;
    typedef node_traits::node_ptr       node_ptr;
    typedef node_traits::const_node_ptr const_node_ptr;

    enum { link_mode = boost::intrusive::normal_link };

    static pointer to_value_ptr(node_ptr n)
    {
        return n;
    }

    static const_pointer to_value_ptr(const_node_ptr n)
    {
        return n;
    }

    static node_ptr to_node_ptr(reference n)
    {
        return &n;
    }

    static const_node_ptr to_node_ptr(const_reference n)
    {
        return &n;
    }
};

struct deleter
{
    template<typename T_>
    void operator()(T_* ptr)
    {
        delete ptr;
    }
};

typedef boost::intrusive::list<my_list_node, boost::intrusive::value_traits<my_list_value_traits> > list_type;

BOOST_AUTO_TEST_CASE(insertion)
{
    list_type l;
    my_list_node a[] = { 3, 1, 2 };
    l.push_back(a[0]);
    BOOST_CHECK_EQUAL(l.size(), 1);
    l.push_back(a[1]);
    BOOST_CHECK_EQUAL(l.size(), 2);
    l.push_back(a[2]);
    BOOST_CHECK_EQUAL(l.size(), 3);
}

BOOST_AUTO_TEST_CASE(iteration_and_sorting)
{
    list_type l;
    my_list_node a[] = { 3, 1, 2 };
    l.push_back(a[0]);
    BOOST_CHECK_EQUAL(l.size(), 1);
    l.push_back(a[1]);
    BOOST_CHECK_EQUAL(l.size(), 2);
    l.push_back(a[2]);
    BOOST_CHECK_EQUAL(l.size(), 3);
    {
        list_type::const_iterator i(l.begin());
        BOOST_CHECK(i != l.end());
        BOOST_CHECK_EQUAL(static_cast<int>(*i), a[0]);
        ++i;
        BOOST_CHECK(i != l.end());
        BOOST_CHECK_EQUAL(static_cast<int>(*i), a[1]);
        ++i;
        BOOST_CHECK(i != l.end());
        BOOST_CHECK_EQUAL(static_cast<int>(*i), a[2]);
        ++i;
        BOOST_CHECK(i == l.end());
    }

    l.sort();

    {
        list_type::const_iterator i(l.begin());
        BOOST_CHECK(i != l.end());
        BOOST_CHECK_EQUAL(static_cast<int>(*i), 1);
        ++i;
        BOOST_CHECK(i != l.end());
        BOOST_CHECK_EQUAL(static_cast<int>(*i), 2);
        ++i;
        BOOST_CHECK(i != l.end());
        BOOST_CHECK_EQUAL(static_cast<int>(*i), 3);
        ++i;
        BOOST_CHECK(i == l.end());
    }
}

BOOST_AUTO_TEST_CASE(removal)
{
    list_type l;
    l.push_back(*new my_list_node(3));
    BOOST_CHECK_EQUAL(l.size(), 1);
    l.push_back(*new my_list_node(1));
    BOOST_CHECK_EQUAL(l.size(), 2);
    l.push_back(*new my_list_node(2));
    BOOST_CHECK_EQUAL(l.size(), 3);

    l.pop_back_and_dispose(deleter());
    BOOST_CHECK_EQUAL(l.size(), 2);
    l.pop_back_and_dispose(deleter());
    BOOST_CHECK_EQUAL(l.size(), 1);
    l.pop_back_and_dispose(deleter());
    BOOST_CHECK_EQUAL(l.size(), 0);
}