因此,作为我之前的数十万人,我正在 С++ 中实现双向链表。 这是一个
Node
和 List
结构:
struct Node {
std::shared_ptr<Node> prev, next;
int data;
Node(int data) : data(data), next(nullptr), prev(nullptr){};
Node(int data, std::shared_ptr<Node> prev, std::shared_ptr<Node> next)
: data(data), prev(prev), next(next){};
~Node(){};
};
struct List {
std::shared_ptr<Node> head, tail;
size_t size;
// some methods ...
void remove(int data);
List();
List(std::initializer_list<int> list);
List(size_t s, int data = 0);
~List();
};
如您所见,我使用共享指针来存储下一个和上一个节点。
所以现在我正在实现
remove
的List
方法,我想知道是否有必要删除节点来使其next
和prev
指针无效。
应该是这样的:
// value - desired number to remove
if (curr->data == value) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
std::shared_ptr<Node> tmp = curr;
curr = curr->next;
tmp->prev = nullptr;
tmp->next = nullptr;
tmp = nullptr;
size--;
}
这取决于你想做什么。
您是否希望列表的用户能够在内存中保存对节点对象的引用,即使列表已经删除了它们(而不是“仅”有效负载数据)? 在这种情况下,这些行就足够了:
if (curr->data == value) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
size--;
}
(但是您可能还想使 prev 和 next 指针无效,我将在稍后解释。)
之前由列表管理的节点对象仅在没有其他
shared_ptr
实例再持有对它的引用时才会被销毁和释放。
我把解释留给cppreference.com:
当发生以下任一情况时,对象将被销毁并释放其内存:
- 拥有该对象的最后剩余的shared_ptr被销毁;
- 拥有该对象的最后一个剩余的shared_ptr通过operator=或reset()分配另一个指针。
参见:https://en.cppreference.com/w/cpp/memory/shared_ptr
如果列表的用户应该能够将节点对象保留在内存中,那就很好。
但是,如果您绝对希望在从列表中删除节点对象时销毁该节点对象,即使列表的用户已经访问了该节点,您可能需要重新考虑列表的设计。有几种方法可以解决这个问题。
使用共享指针时,一种(通常非常糟糕)的方法当然是删除管理节点的所有剩余共享指针。但这可能会变得非常乏味且不可行,因为您需要保持对列表中这些引用的可访问性。而且您几乎无法影响列表中的用户将如何使用他们的共享指针。所以基本上你可以完全忘记这种方法。
您可以研究弱指针的使用,它创建对对象的“临时”共享指针引用,请参阅:https://en.cppreference.com/w/cpp/memory/weak_ptr .
或者您可以不使用共享指针来管理节点。您的节点将保存对其他节点的引用,例如,通过原始指针
Node*
(注意内存管理!)或使用唯一指针,请参阅:https://en.cppreference.com/w/cpp/memory/unique_ptr 。然而,使用唯一指针只能从一侧起作用(只允许一个引用)。请注意不要意外地将 unique_ptr
投射到 shared_ptr
。
无论如何,不要忘记注意您返回给用户的节点对象。如果要将节点保留在内存中,但只是将其从列表中删除(如第一种情况),则需要使节点的
next
和 prev
指针无效,即将它们设置为 nullptr
。 (就像您之前所做的那样。)否则您将在列表之外有一个节点,该节点可以像节点一样访问该列表。这与列表的直观使用相冲突,并且可能会产生一些令人讨厌的错误和意大利面条式代码。
但是,如果您永远不会以任何方式将指向列表中节点对象的共享指针返回给用户,则不需要使当前节点的上一个和下一个无效,因为在对它的所有共享引用都被删除之后,它将被销毁。重置。由于只有两个共享指针指向一个节点,因此这很容易管理。通常,您不会将列表节点对象返回给用户,而是返回节点所持有的对象的(硬)引用。