c++ - 侵入式、循环、无分支、双向链表——如何有列表来识别节点成员字段？

Question

我想要做的是允许用户将列表节点指定为将添加到列表中的类的成员字段。目前，这是通过使用 offsetof() 的宏来完成的，这意味着成员节点必须是公共的。理想情况下，我希望能够以某种方式指定，作为每个linked_list 声明的一部分，作为模板参数，哪个成员字段应该用作节点。boost::intrusive似乎可以管理它，但我不太明白他们是如何做到的。

要求列表函数是无分支的（没有指针比较，平台具有非常非常慢的分支机制）并且列表是侵入性的并且允许对象同时成为多个列表的成员。

//////////////////////////////////////////////////////////////////////
// linked_list.h

#pragma once

//////////////////////////////////////////////////////////////////////

#include <cstddef>
#include <functional>

//////////////////////////////////////////////////////////////////////

struct list_node
{
    list_node *next;
    list_node *prev;
};

//////////////////////////////////////////////////////////////////////

template<typename T, size_t off> struct linked_list
{
    //////////////////////////////////////////////////////////////////////

    static list_node const *get_node(T const *o)
    {
        return reinterpret_cast<list_node const *>(reinterpret_cast<char const *>(o) + off);
    }

    //////////////////////////////////////////////////////////////////////

    static list_node *get_node(T *o)
    {
        return reinterpret_cast<list_node *>(reinterpret_cast<char *>(o) + off);
    }

    //////////////////////////////////////////////////////////////////////

    static T const *get_object(list_node const *node)
    {
        return reinterpret_cast<T const *>(reinterpret_cast<char const *>(node) - off);
    }

    //////////////////////////////////////////////////////////////////////

    static T *get_object(list_node *node)
    {
        return reinterpret_cast<T *>(reinterpret_cast<char *>(node) - off);
    }

    //////////////////////////////////////////////////////////////////////

    list_node root;

    //////////////////////////////////////////////////////////////////////

    linked_list()
    {
        root.next = &root;
        root.prev = &root;
    }

    //////////////////////////////////////////////////////////////////////

    void push_front(T *obj)
    {
        list_node *node = get_node(obj);
        root.next->prev = node;
        node->next = root.next;
        node->prev = &root;
        root.next = node;
    }

    //////////////////////////////////////////////////////////////////////

    void push_front(T &obj)
    {
        list_node *node = get_node(&obj);
        root.next->prev = node;
        node->next = root.next;
        node->prev = &root;
        root.next = node;
    }

    //////////////////////////////////////////////////////////////////////

    void push_back(T *obj)
    {
        list_node *node = get_node(obj);
        node->prev = root.prev;
        node->next = &root;
        root.prev->next = node;
        root.prev = node;
    }

    //////////////////////////////////////////////////////////////////////

    void push_back(T &obj)
    {
        list_node *node = get_node(&obj);
        node->prev = root.prev;
        node->next = &root;
        root.prev->next = node;
        root.prev = node;
    }

    //////////////////////////////////////////////////////////////////////

    void insert_before(T *pos, T *obj)
    {
        list_node *node = get_node(obj);
        list_node *n = get_node(pos);
        n->prev->next = node;
        node->prev = n->prev;
        n->prev = node;
        node->next = n;
    }

    //////////////////////////////////////////////////////////////////////

    void insert_before(T &pos, T &obj)
    {
        list_node *node = get_node(&obj);
        list_node *n = get_node(&pos);
        n->prev->next = node;
        node->prev = n->prev;
        n->prev = node;
        node->next = n;
    }

    //////////////////////////////////////////////////////////////////////

    void insert_after(T *pos, T *obj)
    {
        list_node *node = get_node(obj);
        list_node *n = get_node(pos);
        n->next->prev = node;
        node->next = n->next;
        n->next = node;
        node->prev = n;
    }

    //////////////////////////////////////////////////////////////////////

    void insert_after(T &pos, T &obj)
    {
        list_node *node = get_node(&obj);
        list_node *n = get_node(&pos);
        n->next->prev = node;
        node->next = n->next;
        n->next = node;
        node->prev = n;
    }

    //////////////////////////////////////////////////////////////////////

    void remove(T *obj)
    {
        list_node *node = get_node(obj);
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    //////////////////////////////////////////////////////////////////////

    void remove(T &obj)
    {
        list_node *node = get_node(&obj);
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    //////////////////////////////////////////////////////////////////////

    T *pop_back()
    {
        list_node *node = root.prev;
        node->prev->next = node->next;
        node->next->prev = node->prev;
        return get_object(node);
    }

    //////////////////////////////////////////////////////////////////////

    T *pop_front()
    {
        list_node *node = root.next;
        node->next->prev = node->prev;
        node->prev->next = node->next;
        return get_object(node);
    }

    //////////////////////////////////////////////////////////////////////

    bool empty() const
    {
        return root.next == &root;
    }

    //////////////////////////////////////////////////////////////////////

    void clear()
    {
        root.next = root.prev = &root;
    }

    //////////////////////////////////////////////////////////////////////

    T *head() const
    {
        return get_object(root.next);
    }

    //////////////////////////////////////////////////////////////////////

    T *tail() const
    {
        return get_object(root.prev);
    }

    //////////////////////////////////////////////////////////////////////

    T const *end()
    {
        return get_object(&root);
    }

    //////////////////////////////////////////////////////////////////////

    T *next(T *i) const
    {
        return get_object(get_node(i)->next);
    }

    //////////////////////////////////////////////////////////////////////

    T *prev(T *i) const
    {
        return get_object(get_node(i)->prev);
    }

    //////////////////////////////////////////////////////////////////////

    bool for_each(std::function<bool (T *)> func)
    {
        for(T *i = head(); i != end(); i = next(i))
        {
            if(!func(i))
            {
                return false;
            }
        }
        return true;
    }

    //////////////////////////////////////////////////////////////////////

    T *find(std::function<bool (T *)> func)
    {
        for(T *i = head(); i != end(); i = next(i))
        {
            if(func(i))
            {
                return i;
            }
        }
        return nullptr;
    }

    //////////////////////////////////////////////////////////////////////

};

//////////////////////////////////////////////////////////////////////

// Yuck:

#define declare_linked_list(type_name, node_name) \
    linked_list<type_name, offsetof(type_name, node_name)>

#define typedef_linked_list(type_name, node_name) \
    typedef declare_linked_list(type_name, node_name)

客户端代码如下所示：

//////////////////////////////////////////////////////////////////////
// main.cpp

#include <stdio.h>
#include <random>
#include "linked_list.h"

struct foo
{
    foo() : i(rand() % 10) { }

    int i;

    list_node node1;    // would like it if these could be made private
    list_node node2;    // but the nasty macros need to see inside...
    list_node node3;    // getting rid of the macros would be even better
};

// None of these 3 options are very nice:

// 1. declare a list with the macro
declare_linked_list(foo, node1) list1;

// 2. or via a typedef
typedef_linked_list(foo, node2) list2_t;
list2_t list2;

// 3. or very wordy non-macro declaration
linked_list<foo, offsetof(foo, node3)> list3;

int main(int, char **)
{
    printf("Begin\n");

    foo foos[10];

    for(int i=0; i<10; ++i)
    {
        list1.push_back(foos[i]);
        list2.push_back(foos[i]);
        list3.push_back(foos[i]);
    }

    int sum = 0;
    int n = 0;
    // but this for loop is clear and readable and has very low overhead
    for(foo *i = list1.head(); i != list1.end(); i = list1.next(i))
    {
        sum += i->i;
    }
    printf("Total: %d\n", sum);

    list2.remove(foos[2]);

    n = 0;
    sum = 0;
    for(foo *i = list2.head(); i != list2.end(); i = list2.next(i))
    {
        sum += i->i;
    }
    printf("Total2: %d\n", sum);

    getchar();
    return 0;
}

[编辑] 好的，使用指向成员模板参数的指针会更好：

template<typename T, list_node T::* node> struct linked_list
{
    //////////////////////////////////////////////////////////////////////

    static list_node const *get_node(T const *o)
    {
        return reinterpret_cast<list_node const *>
            (reinterpret_cast<char const *>(o) + offsetof(T, *node));
    }

    //////////////////////////////////////////////////////////////////////

    static list_node *get_node(T *o)
    {
        return reinterpret_cast<list_node *>
            (reinterpret_cast<char *>(o) + offsetof(T, *node));
    }

    //////////////////////////////////////////////////////////////////////

    static T const *get_object(list_node const *n)
    {
        return reinterpret_cast<T const *>
            (reinterpret_cast<char const *>(n) - offsetof(T, *node));
    }

    //////////////////////////////////////////////////////////////////////

    static T *get_object(list_node *n)
    {
        return reinterpret_cast<T *>
            (reinterpret_cast<char *>(n) - offsetof(T, *node));
    }

因此您可以声明如下列表：

linked_list<foo, &foo::node1> list1;

所以我们（大部分）摆脱了丑陋的声明语法，尽管我仍然找不到让它们成为私有的方法。看起来 boost::intrusive 也要求它们公开。

score 1 · Accepted Answer

这是一个技巧，它允许成员和结构之间的双射映射，在运行时仅对常量进行指针运算。 static_assert( std::is_pod<T>::value, "POD needed!" );可能是个好主意：

template<typename T, typename N, N T::* member>
struct member_access {
  static N& ContainerToMember( T& t ) { return t.*member; }
  static N const& ContainerToMember( T const& t ) { return t.*member; }
  template<T* ptr=nullptr>
  static constexpr std::size_t offset_of() {
return reinterpret_cast<std::size_t>(reinterpret_cast<char*>(&((ptr)->*member)));
  }
  static T& MemberToContainer( N& n ) {
    return *reinterpret_cast<T*>(reinterpret_cast<char*>(&n)-offset_of());
  }
  static T const& MemberToContainer( N const& n ) {
    return *reinterpret_cast<T const*>(reinterpret_cast<char const*>(&n)-offset_of());
  }
};

这摆脱了你的offsetof要求。

隐私很难。隐私类型系统中存在显式的专业化副作用漏洞，但它会导致运行时成员指针，并且我们需要编译时间值。

更好的方法可能是将链接列表填充到一些元编程中：

template< typename T, unsigned index >
struct list_node:list_node<T, index-1> {
  list_node* next;
  list_node* prev;
  T* self() { static_cast<T*>(this); }
  T const* self() const { static_cast<T const*>(this); }
};
template<typename T>
struct list_node<T, 0> {
  list_node* next;
  list_node* prev;
  T* self() { static_cast<T*>(this); }
  T const* self() const { static_cast<T const*>(this); }
};
template<typename T, unsigned N>
struct listable : list_node<T, N-1> {};
template<typename T>
struct listable<T, 0> {};

然后只需创建您的可列出数据，例如：

struct data: listable<data, 10> {
  std::string s;
};

然后我们可以这样做：

template<unsigned N, typename T>
list_node<T, N>& get_node( T& t ) { return t; }
template<unsigned N, typename T>
list_node<T, N> const& get_node( T const& t ) { return t; }
template<unsigned N, typename T>
T& get_data( list_node<T, N>& n ) { return *n.self(); }
template<unsigned N, typename T>
T const& get_data( list_node<T, N> const& n ) { return *n.self(); }

这都是合法的 C++11。

template<typename T, unsigned index>
struct linked_list {
  typedef list_node<T, index> node;
};

这有点好。缺点：list_nodefor eachlinked_list是不同的类型。解决这个问题有点棘手。

next我们可以通过将所有和prev指向 POD 数组的指针推到 topmost 的根之外，从而保持在已定义行为的范围内list_node。然后我们使用指向它的指针。我们可以合法地在该数组中进行指针运算，并且指向最原始结构的第一个元素的指针可以合法地重新解释为指向该结构的指针。

从那里，我们可以直接static_cast到 a T*（这可能根本没有指针值的二进制变化）。

struct link { link* next; link* prev; };

template<typename T, unsigned N>
struct listable {
  std::array<link, N> links;
  static listable* array_to_list( std::array<link, N>* a ) { return reinterpret_cast<listable>(a); }
  template<unsigned I>
  static listable* link_to_list( link* l ) {
    return array_to_list( reinterpret_cast<std::array<link, N>>(l - I) );
  }
  template<unsigned I>
  link* get_link() { return &links[I]; }
  T* listable_to_T() {
    static_assert( std::is_base_of< listable, T >::value, "CRTP vailure" );
    return static_cast<T*>(this);
  }
  template<unsigned I>
  static T* link_to_T(link* l) {
    return link_to_list<I>(l)->listable_to_T()
  }
};

最多要求指向第一个元素的指针和指向数组的指针布局兼容（我希望如此！）

同样，在此模型下，您的链接可列出数据会：

struct Bob : listable<Bob, 10> {};

说有 10 个嵌入列表Bob。从 a 转换Bob为 alink*涉及调用bob.get_link<5>()，而从 a 转换link*为 a Bob*is listable<Bob, 10>::link_to_T<5>( l )，假设我们正在讨论子列表 5。

c++ - 侵入式、循环、无分支、双向链表——如何有列表来识别节点成员字段？

1 回答 1

Related

Reference