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

标签 c++ templates linked-list circular-list branch-prediction

代码发布在这里:https://ideone.com/ul2PiS

我想做的是允许用户将列表节点指定为将添加到列表中的类的成员字段。目前，这是通过使用 offsetof() 的宏完成的，这意味着成员节点必须是公共(public)的。理想情况下，我希望能够以某种方式指定，作为每个 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;

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

最佳答案

这里有一些 hack 允许成员和结构之间的双射映射，在运行时对常量进行指针运算。 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_node对于每个 linked_list是不同的类型。解决这个问题有点棘手。

我们可以通过插入所有 next 来保持在已定义行为的范围内和 prev指向超出最顶层 list_node 根的 POD 数组的指针.然后我们使用指向它的指针。我们可以合法地在该数组内进行指针运算，指向最古老结构的第一个元素的指针可以合法地重新解释为指向该结构的指针。

据此，我们可以 static_cast下降到 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> {};

表示 Bob 中有 10 个嵌入列表.从 Bob 转换到 link*涉及调用 bob.get_link<5>() , 同时从 link* 转换到 Bob*是listable<Bob, 10>::link_to_T<5>( l ) ，假设我们正在谈论子列表 5。

关于c++ - 侵入式、循环式、无分支式、双向链表——如何让链表识别节点成员字段？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22256092/

上一篇：c++ - 使用模板特化和接口(interface)对实例和原始类型进行统一函数调用

下一篇：c++ - c/c++ 库存位图使用十六进制字母并转换回来

相关文章：

c++ - 在二叉搜索树中插入值

c - 以下程序的输出是什么？如何追踪这样的程序？

java - 打印存储类的链表时出现问题

c++ - 我应该将这些方法声明为 const 吗？

c++ - 基本的 C 风格字符串内存分配

c++ - 解决方法 clang 警告 -Wambiguous-member-template

c++将类与寺庙结合起来 - 声明其他功能？

c++ - 如何删除最后一个逗号？

c++ - ##(双哈希)在预处理器指令中起什么作用？

c++ - 返回不同的数据类型而不明确指定数据类型

©2024 IT工具网  联系我们