如何编写类似于内核的c++风格的双链表实现list_head
Howto write a c++ style double linked list implementation similar to kernels list_head
我正在寻找一种将双 linked 列表结构转换为类型保存 C++ 结构的方法。我想转换类似于 Birds Double linked list 或类似 Linux 的 list_head 的内容。特别是我 想在遍历所有成员时摆脱类型转换 。
这些结构的主要特性是：
linked 列表作为包含结构内的 head/node 成员实现。 head/tail 使用与节点相同的结构，因此列表节点条目不需要显式 up 指向列表头的指针，同时仍然可以删除带有 的条目指向节点的指针 (rem_node(p)).
这是我目前使用的：
#include <stdio.h>
#include <iostream>
template <typename b>
struct node {
node<b> *next, *prev;
operator b*() {
return (b*) (this->next);
}
};
template <typename a, typename b>
union llist {
struct {
node<b> head_node;
void *head_padding;
};
struct {
void *tail_padding;
node<b> tail_node;
};
struct {
node<b> *head;
node<b> *null;
node<b> *tail;
};
operator b*() {
return (b*) (this->head);
}
};
template <typename a, typename b>
void
add_head(llist<a,b> &l, node<b> &n)
{
auto *z = l.head;
n.next = z;
n.prev = &l.head_node;
z->prev = &n;
l.head = &n;
}
template <typename b>
void
rem_node(node<b> &n)
{
node<b> *z = n.prev;
node<b> *x = n.next;
z->next = x;
x->prev = z;
n.next = NULL;
n.prev = NULL;
}
template <typename a, typename b>
void
init_list(llist<a,b> &l)
{
l.head = &l.tail_node;
l.null = NULL;
l.tail = &l.head_node;
}
struct c1 {
node<c1> n;
};
struct c0 {
llist<c0, c1> l;
};
int main(int argc, char **argv) {
c0 v0;
c1 e0, e1, e2;
c1 *i0;
init_list(v0.l);
add_head(v0.l, e0.n);
add_head(v0.l, e1.n);
add_head(v0.l, e2.n);
#define WALK_LIST(i,list) for(i=list; i->n.next; i=i->n)
WALK_LIST(i0,v0.l) {
std::cout << i0 << "\n";
}
rem_node(e1.n);
std::cout << "\n";
WALK_LIST(i0,v0.l) {
std::cout << i0 << "\n";
}
return 0;
}
operator b*() { return (b*) (this->next);} 之所以有效，是因为列表 head/node 结构位于包含结构 c1/c2 的 开头 。我真正想要的是在代码中的任何地方使用它（伪代码）：
struct c1 {
int pad;
node<c1> n;
};
struct c0 {
int pad;
llist<c0, c1> l;
};
是否有一些更聪明的方法来实现这种风格的双 linked 列表？
是否有一种方法可以让我跳过类型转换？
我不是在搜索 std::list 或类似的东西，我只是在搜索 list_head 样式的双 linked 列表如何以类型保存方式在 c++ 中表达。也许没有这种可能。虽然有一个指向 class C::*p 的成员的指针可以作为模板参数给出，但没有它的逆（类似于 container_of 的东西）。或者有没有？
编辑：
（下面的答案）
经过一番思考，我想出了以下
我现在满意的结构：
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
* https://github.com/BIRD/bird/blob/470efcb98cb33de2d5636679eb0f72c88280d6b8/lib/lists.h#L12
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
node<b> *z = this->prev;
node<b> *x = this->next;
z->next = x;
x->prev = z;
this->next = NULL;
this->prev = NULL;
}
};
template <typename b, node<b> (b::* p)>
union llist {
struct {
node<b> head_node;
void *head_padding;
};
struct {
void *tail_padding;
node<b> tail_node;
};
struct {
node<b> *head;
node<b> *null;
node<b> *tail;
};
llist()
{
this->head = &this->tail_node;
this->null = NULL;
this->tail = &this->head_node;
}
void
add_head(node<b> &n)
{
node<b> *z = this->head;
n.next = z;
n.prev = &(this->head_node);
z->prev = &n;
this->head = &n;
}
static b *container_of(node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
node<b> *i;
};
lit begin() const { return lit(this->head); }
lit end() const { return lit(this->tail->next); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
for (auto &i: list0.l)
cout << &i << "\n";
cout << "\n";
e->n.rem_node();
for (auto &i: list1.l)
cout << &i << "\n";
}
return 0;
}
以上是基于Bird的双重link名单。以下是基于 linux
list_head and list_head functions:
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
*
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
next->prev = prev;
prev->next = next;
}
};
template <typename b, node<b> (b::* p)>
struct llist {
node<b> head;
llist()
{
head.prev = &head;
head.next = &head;
}
void
add_head(node<b> &n)
{
node<b> *prev, *next;
prev = &head;
next = head.next;
next->prev = &n;
n.next = next;
n.prev = prev;
prev->next = &n;
}
static b *container_of(const node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(const node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
const node<b> *i;
};
lit begin() const { return lit(this->head.next); }
lit end() const { return lit(&this->head); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
e->n.rem_node();
cout << "\nlist0:\n";
for (auto &i: list0.l) {
cout << &i << "\n";
}
cout << "\nlist1:\n";
for (auto &i: list1.l) {
cout << &i << "\n";
}
}
return 0;
}
经过一番思考，我找到了一种方法来定义
container_of() 使用指向成员模板参数的指针以模板方式运行。
- 节点可以是多个列表的一部分
- 每个节点 2 个指针，每个列表头 3 个指针
- 无需指向列表的指针即可删除节点
由于 container_of()，实现不是类型保存。特别是有两种类型的错误：您可以将节点添加到错误类型的列表（可以通过添加更多模板签名来修复）和声明具有错误基类型的节点（无法修复，因为您无法确定包含类型并检查在编译时（或者你可以吗？））：
//
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
* https://github.com/BIRD/bird/blob/470efcb98cb33de2d5636679eb0f72c88280d6b8/lib/lists.h#L12
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
node<b> *z = this->prev;
node<b> *x = this->next;
z->next = x;
x->prev = z;
this->next = NULL;
this->prev = NULL;
}
};
template <typename b, node<b> (b::* p)>
union llist {
struct {
node<b> head_node;
void *head_padding;
};
struct {
void *tail_padding;
node<b> tail_node;
};
struct {
node<b> *head;
node<b> *null;
node<b> *tail;
};
llist()
{
this->head = &this->tail_node;
this->null = NULL;
this->tail = &this->head_node;
}
void
add_head(node<b> &n)
{
node<b> *z = this->head;
n.next = z;
n.prev = &(this->head_node);
z->prev = &n;
this->head = &n;
}
static b *container_of(node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
node<b> *i;
};
lit begin() const { return lit(this->head); }
lit end() const { return lit(this->tail->next); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
for (auto &i: list0.l)
cout << &i << "\n";
cout << "\n";
e->n.rem_node();
for (auto &i: list1.l)
cout << &i << "\n";
}
return 0;
}
版本基于 list_head 没有 union:
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
*
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
next->prev = prev;
prev->next = next;
}
};
template <typename b, node<b> (b::* p)>
struct llist {
node<b> head;
llist()
{
head.prev = &head;
head.next = &head;
}
void
add_head(node<b> &n)
{
node<b> *prev, *next;
prev = &head;
next = head.next;
next->prev = &n;
n.next = next;
n.prev = prev;
prev->next = &n;
}
static b *container_of(const node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(const node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
const node<b> *i;
};
lit begin() const { return lit(this->head.next); }
lit end() const { return lit(&this->head); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
e->n.rem_node();
cout << "\nlist0:\n";
for (auto &i: list0.l) {
cout << &i << "\n";
}
cout << "\nlist1:\n";
for (auto &i: list1.l) {
cout << &i << "\n";
}
}
return 0;
}
简化您自己的答案，特别是删除一些非法代码（通过联合输入双关语）：
struct node
{
node* prev;
node* next;
};
struct llist
{
node head_node;
node tail_node;
llist()
{
head_node.prev = nullptr;
head_node.next = &tail_node;
tail_node.prev = &head_node;
tail_node.next = nullptr;
}
void add_head(node& n)
{
head_node.next->prev = &n;
n.next = head_node.next;
head_node.next = &n;
n.prev = &this->head_node;
}
};
到目前为止，您根本不需要任何模板...
template <typename b> // function now needs to be a template itself...
static b* container_of(node& ptr)
{
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
一开始，p没有定义：
template <typename b>
static b* container_of(node& ptr, node b::*p)
{
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
containnode c;
containnode* cn = llist::container_of<containnode>(c.n, &containnode::n);
containnode* cm = llist::container_of<containnode>(c.m, &containnode::m);
但是，这非常危险！想象一下，如果您从列表中获取节点并现在使用错误的成员函数指针会发生什么：
containnode* BAD = llist::container_of<containnode>(c.n, &containnode::m);
// ^ ^
而是考虑将数据直接存储在节点本身（重新引入模板参数！）：
template <typename T>
struct node
{
node* prev;
node* next;
T data;
};
template <typename T>
struct llist
{
node<T> head_node;
node<T> tail_node;
void add_head(node<T>& n);
// container_of dropped, rest unchanged
};
这限制了可以使用的类型（事实上，T 需要是哨兵的默认构造函数，不过你可以提供一个合适的构造函数来绕过这个限制）。
如果要将同一个元素插入多个列表，请通过指针进行：
Element e;
node<Element*> n0(&e); // appropriate constructor provided
node<Element*> n1(&e); // appropriate constructor provided
现在您可以将 n0 和 n1 添加到不同的列表中...
我正在寻找一种将双 linked 列表结构转换为类型保存 C++ 结构的方法。我想转换类似于 Birds Double linked list 或类似 Linux 的 list_head 的内容。特别是我 想在遍历所有成员时摆脱类型转换 。
这些结构的主要特性是：
linked 列表作为包含结构内的 head/node 成员实现。 head/tail 使用与节点相同的结构，因此列表节点条目不需要显式 up 指向列表头的指针，同时仍然可以删除带有 的条目指向节点的指针 (rem_node(p)).
这是我目前使用的：
#include <stdio.h>
#include <iostream>
template <typename b>
struct node {
node<b> *next, *prev;
operator b*() {
return (b*) (this->next);
}
};
template <typename a, typename b>
union llist {
struct {
node<b> head_node;
void *head_padding;
};
struct {
void *tail_padding;
node<b> tail_node;
};
struct {
node<b> *head;
node<b> *null;
node<b> *tail;
};
operator b*() {
return (b*) (this->head);
}
};
template <typename a, typename b>
void
add_head(llist<a,b> &l, node<b> &n)
{
auto *z = l.head;
n.next = z;
n.prev = &l.head_node;
z->prev = &n;
l.head = &n;
}
template <typename b>
void
rem_node(node<b> &n)
{
node<b> *z = n.prev;
node<b> *x = n.next;
z->next = x;
x->prev = z;
n.next = NULL;
n.prev = NULL;
}
template <typename a, typename b>
void
init_list(llist<a,b> &l)
{
l.head = &l.tail_node;
l.null = NULL;
l.tail = &l.head_node;
}
struct c1 {
node<c1> n;
};
struct c0 {
llist<c0, c1> l;
};
int main(int argc, char **argv) {
c0 v0;
c1 e0, e1, e2;
c1 *i0;
init_list(v0.l);
add_head(v0.l, e0.n);
add_head(v0.l, e1.n);
add_head(v0.l, e2.n);
#define WALK_LIST(i,list) for(i=list; i->n.next; i=i->n)
WALK_LIST(i0,v0.l) {
std::cout << i0 << "\n";
}
rem_node(e1.n);
std::cout << "\n";
WALK_LIST(i0,v0.l) {
std::cout << i0 << "\n";
}
return 0;
}
operator b*() { return (b*) (this->next);} 之所以有效，是因为列表 head/node 结构位于包含结构 c1/c2 的 开头 。我真正想要的是在代码中的任何地方使用它（伪代码）：
struct c1 {
int pad;
node<c1> n;
};
struct c0 {
int pad;
llist<c0, c1> l;
};
是否有一些更聪明的方法来实现这种风格的双 linked 列表？
是否有一种方法可以让我跳过类型转换？
我不是在搜索 std::list 或类似的东西，我只是在搜索
list_head样式的双 linked 列表如何以类型保存方式在 c++ 中表达。也许没有这种可能。虽然有一个指向 class C::*p 的成员的指针可以作为模板参数给出，但没有它的逆（类似于container_of的东西）。或者有没有？
编辑：
（下面的答案） 经过一番思考，我想出了以下 我现在满意的结构：
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
* https://github.com/BIRD/bird/blob/470efcb98cb33de2d5636679eb0f72c88280d6b8/lib/lists.h#L12
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
node<b> *z = this->prev;
node<b> *x = this->next;
z->next = x;
x->prev = z;
this->next = NULL;
this->prev = NULL;
}
};
template <typename b, node<b> (b::* p)>
union llist {
struct {
node<b> head_node;
void *head_padding;
};
struct {
void *tail_padding;
node<b> tail_node;
};
struct {
node<b> *head;
node<b> *null;
node<b> *tail;
};
llist()
{
this->head = &this->tail_node;
this->null = NULL;
this->tail = &this->head_node;
}
void
add_head(node<b> &n)
{
node<b> *z = this->head;
n.next = z;
n.prev = &(this->head_node);
z->prev = &n;
this->head = &n;
}
static b *container_of(node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
node<b> *i;
};
lit begin() const { return lit(this->head); }
lit end() const { return lit(this->tail->next); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
for (auto &i: list0.l)
cout << &i << "\n";
cout << "\n";
e->n.rem_node();
for (auto &i: list1.l)
cout << &i << "\n";
}
return 0;
}
以上是基于Bird的双重link名单。以下是基于 linux list_head and list_head functions:
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
*
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
next->prev = prev;
prev->next = next;
}
};
template <typename b, node<b> (b::* p)>
struct llist {
node<b> head;
llist()
{
head.prev = &head;
head.next = &head;
}
void
add_head(node<b> &n)
{
node<b> *prev, *next;
prev = &head;
next = head.next;
next->prev = &n;
n.next = next;
n.prev = prev;
prev->next = &n;
}
static b *container_of(const node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(const node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
const node<b> *i;
};
lit begin() const { return lit(this->head.next); }
lit end() const { return lit(&this->head); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
e->n.rem_node();
cout << "\nlist0:\n";
for (auto &i: list0.l) {
cout << &i << "\n";
}
cout << "\nlist1:\n";
for (auto &i: list1.l) {
cout << &i << "\n";
}
}
return 0;
}
经过一番思考，我找到了一种方法来定义
container_of() 使用指向成员模板参数的指针以模板方式运行。
- 节点可以是多个列表的一部分
- 每个节点 2 个指针，每个列表头 3 个指针
- 无需指向列表的指针即可删除节点
由于 container_of()，实现不是类型保存。特别是有两种类型的错误：您可以将节点添加到错误类型的列表（可以通过添加更多模板签名来修复）和声明具有错误基类型的节点（无法修复，因为您无法确定包含类型并检查在编译时（或者你可以吗？））：
//
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
* https://github.com/BIRD/bird/blob/470efcb98cb33de2d5636679eb0f72c88280d6b8/lib/lists.h#L12
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
node<b> *z = this->prev;
node<b> *x = this->next;
z->next = x;
x->prev = z;
this->next = NULL;
this->prev = NULL;
}
};
template <typename b, node<b> (b::* p)>
union llist {
struct {
node<b> head_node;
void *head_padding;
};
struct {
void *tail_padding;
node<b> tail_node;
};
struct {
node<b> *head;
node<b> *null;
node<b> *tail;
};
llist()
{
this->head = &this->tail_node;
this->null = NULL;
this->tail = &this->head_node;
}
void
add_head(node<b> &n)
{
node<b> *z = this->head;
n.next = z;
n.prev = &(this->head_node);
z->prev = &n;
this->head = &n;
}
static b *container_of(node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
node<b> *i;
};
lit begin() const { return lit(this->head); }
lit end() const { return lit(this->tail->next); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
for (auto &i: list0.l)
cout << &i << "\n";
cout << "\n";
e->n.rem_node();
for (auto &i: list1.l)
cout << &i << "\n";
}
return 0;
}
版本基于 list_head 没有 union:
// g++ -g -std=c++11 81_list.cpp -o 81_list.exe
// 8< ---------------- 81_list.cpp ------------------
#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <cstddef>
using namespace std;
/***************************************/
/* definition of double linked list
*
*/
template <typename b>
struct node {
node<b> *next, *prev;
void
rem_node()
{
next->prev = prev;
prev->next = next;
}
};
template <typename b, node<b> (b::* p)>
struct llist {
node<b> head;
llist()
{
head.prev = &head;
head.next = &head;
}
void
add_head(node<b> &n)
{
node<b> *prev, *next;
prev = &head;
next = head.next;
next->prev = &n;
n.next = next;
n.prev = prev;
prev->next = &n;
}
static b *container_of(const node<b> &ptr) {
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
struct lit {
lit(const node<b> *i) : i(i) {}
lit & operator++()
{
i = i->next;
return *this;
}
bool operator!=(const lit &that) const
{
return i != that.i;
}
b &operator*()
{
return *container_of(*i);
}
const node<b> *i;
};
lit begin() const { return lit(this->head.next); }
lit end() const { return lit(&this->head); }
};
/*********************************************/
/* example of usage: */
struct containnode {
int pad; /* padding allowed */
node<containnode> n;
node<containnode> m;
};
struct containlist0 {
int pad; /* padding allowed */
llist<containnode, &containnode::n> l;
};
struct containlist1 {
int pad; /* padding allowed */
llist<containnode, &containnode::m> l;
};
int main(int argc, char **argv) {
containlist0 list0;
containlist1 list1;
containnode e0, e1, e2;
containnode *v[3] = { &e0, &e1, &e2 };
/* add to list */
for (auto *e : v) {
list0.l.add_head(e->n);
list1.l.add_head(e->m);
}
/* remove from list0 and print list0 and list1 */
for (auto *e : v) {
e->n.rem_node();
cout << "\nlist0:\n";
for (auto &i: list0.l) {
cout << &i << "\n";
}
cout << "\nlist1:\n";
for (auto &i: list1.l) {
cout << &i << "\n";
}
}
return 0;
}
简化您自己的答案，特别是删除一些非法代码（通过联合输入双关语）：
struct node
{
node* prev;
node* next;
};
struct llist
{
node head_node;
node tail_node;
llist()
{
head_node.prev = nullptr;
head_node.next = &tail_node;
tail_node.prev = &head_node;
tail_node.next = nullptr;
}
void add_head(node& n)
{
head_node.next->prev = &n;
n.next = head_node.next;
head_node.next = &n;
n.prev = &this->head_node;
}
};
到目前为止，您根本不需要任何模板...
template <typename b> // function now needs to be a template itself...
static b* container_of(node& ptr)
{
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
一开始，p没有定义：
template <typename b>
static b* container_of(node& ptr, node b::*p)
{
return (b*) (((char*)&ptr) - (long)&(((b*)0)->*p));
}
containnode c;
containnode* cn = llist::container_of<containnode>(c.n, &containnode::n);
containnode* cm = llist::container_of<containnode>(c.m, &containnode::m);
但是，这非常危险！想象一下，如果您从列表中获取节点并现在使用错误的成员函数指针会发生什么：
containnode* BAD = llist::container_of<containnode>(c.n, &containnode::m);
// ^ ^
而是考虑将数据直接存储在节点本身（重新引入模板参数！）：
template <typename T>
struct node
{
node* prev;
node* next;
T data;
};
template <typename T>
struct llist
{
node<T> head_node;
node<T> tail_node;
void add_head(node<T>& n);
// container_of dropped, rest unchanged
};
这限制了可以使用的类型（事实上，T 需要是哨兵的默认构造函数，不过你可以提供一个合适的构造函数来绕过这个限制）。
如果要将同一个元素插入多个列表，请通过指针进行：
Element e;
node<Element*> n0(&e); // appropriate constructor provided
node<Element*> n1(&e); // appropriate constructor provided
现在您可以将 n0 和 n1 添加到不同的列表中...