如何理解C++中链表的自由列表实现?

Question

我不明白这里的最后几行。

// Singly linked list node with freelist support
template<typename Elem> class Link {
private:
static Link<Elem>* freelist; // Reference to freelist head
public:
Elem element;                // Value for this node
Link* next;                  // Point to next node in list
// Constructors
Link(const Elem& elemval, Link* nextval = NULL)
{ element = elemval; next = nextval; }
Link(Link* nextval = NULL) { next = nextval; }
void* operator new(size_t) { // Overloaded new operator
if (freelist == NULL) return ::new Link; // Create space
Link<Elem>* temp = freelist; // Can take from freelist
freelist = freelist->next;
return temp;                 // Return the link
}
// Overloaded delete operator
void operator delete(void* ptr) {
((Link<Elem>*)ptr)->next = freelist; // Put on freelist
freelist = (Link<Elem>*)ptr;
}
};
// The freelist head pointer is actually created here
template<typename Elem>
Link<Elem>* Link<Elem>::freelist = NULL;

特别是，为什么我们需要在最后一行定义指向指针的指针？Link<Elem>::freelist已经是一个指针，那么为什么我们需要设置另一个指向该指针的指针NULL呢？

有人可以为我澄清这一点吗？我很困惑。

Answer 1

提炼出你的例子，这就是你所拥有的：

class Link {
static Link* freelist;
}
Link* Link::freelist = NULL;

正如评论中提到的，"自由列表头指针实际上是在这里创建的"。第一部分是静态变量freelist的声明，但它实际上并没有定义它。下面的定义模仿声明(并为其提供一个值(。它不会添加另一个级别的指针。

Answer 2

不仅最后两行应该提出问题，而且operator new的实施也应该提出问题。

让我们考虑以下代码：

struct S { 
// ... 
};
auto list = new List<S>;

在这里，new List<S>将调用List<S>::operator new来分配原始内存。它将调用全局::new，并且全局::new将分配内存(带有::operator new(并构造Link，即S和Link*，在其中。然后我们的本地new将在同一内存位置再次构造Link。因此，S将在同一内存位置构造两次。根据S，这可能导致未定义的行为和/或内存泄漏。

简单的例子：

struct S {
S()  { std::cout << "ctor at " << this << 'n'; }
~S() { std::cout << "dtor at " << this << 'n'; }
};
int main() {
auto list = new Link<S>;
delete list;
}

示例输出：

ctor at 0x24b8e80
ctor at 0x24b8e80
dtor at 0x24b8e80

Answer 3

类的静态非常量成员的声明只需要一个外行定义。 静态成员不使用其类对象的存储，因此您必须单独声明和初始化其自己的存储。

class Link {
static Link* freelist; // declaring that such object exists
};
// Shouldn't appear in a header file  to not break One Definition Rule
Link* Link::freelist = nullptr; // initialization

freelist 实际上是一个"全局"变量，可以通过类 Link 的上下文访问，例如Link::freelist它是否是公开的。 在这种特殊情况下，它只是在类对象的所有实例之间共享。