一题引出C++内存管理和设计原则

前言

最近在刷LeetCode,昨天做到了这一题 237. 删除链表中的节点,题目很简单,官方题解中,给出的Java代码如下

1
2
3
4
5
6
7
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
// 作者:LeetCode
// 链接:https://leetcode-cn.com/problems/delete-node-in-a-linked-list/solution/shan-chu-lian-biao-zhong-de-jie-dian-by-leetcode/
// 来源:力扣(LeetCode)

可以看出,官方题解的思路是直接将自身替换成了下一个节点

我平时使用C++来做题,但如果简单的将上述代码修改成C++就可能会导致严重的内存泄漏事故

C++内存释放

大家都知道Java是有垃圾回收也就是GC的,所以上述代码在Java中是完全没有问题的,因为被替换掉的节点会由GC来释放

而在C++中,每一个被new出来的原生指针(Raw Pinter)都必须使用delete释放,不释放会内存泄漏

那我们直接写成下面这样

1
2
3
4
5
6
7
8
9
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* del = node->next;
node->val = node->next->val;
node->next = node->next->next;
delete del;
}
};

可能到这里,大部分人就觉得OK了,万无一失了。

但C++中的对象是分为静态分配动态分配

确实在大部分情况下是没有问题了,但,delete只能用于释放堆指针,也就是new出来的指针,而不能用于栈指针。

所以以下代码在VC++ Debug下会抛出_CrtIsValidHeapPointer(block)is_block_type_valid(header->block_use)异常,因为C运行时检测到了你要delete的指针不是一个堆指针

1
2
3
4
5
6
7
8
9
10
11
int main() {
ListNode a(4), b(5), c(1), d(9);
a.next = &b;
b.next = &c;
c.next = &d;

Solution solution;
solution.deleteNode(&b);

return 0;
}

当然有人要说了,这是个链表节点啊,谁会静态分配啊,静态分配不就没意义了嘛!

但为了以防万一,还是需要使用设计来限制NodeList只能动态分配

只能动态分配

简单来说,只需要将构造、析构函数设为protected属性,再将将动态分配的职责给到静态函数即可

1
2
3
4
5
6
7
8
struct ListNode {
protected:
ListNode(int x) : val(x), next(NULL) {}
public:
int val;
ListNode* next;
static ListNode* create(int x) { return new ListNode(x); }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
// ListNode a(4); 错误: 构造函数不可访问
ListNode* a = ListNode::create(4);
ListNode* b = ListNode::create(5);
ListNode* c = ListNode::create(1);
ListNode* d = ListNode::create(9);

a->next = b;
b->next = c;
c->next = d;

Solution solution;
solution.deleteNode(b);

return 0;
}

这样就可以保证deleteNode函数不会delete到栈指针了

设计原则

存在的错误

经过上面的改造,大部分人可能就觉得没有啥问题了。但官方给出的“删除”真的是删除吗?

很显然这不是真正的删除了该删除的节点,而是将原节点修改了值。

在Dbueg下看到,deleteNode函数从语义上看是删除了b节点,但实际上,b节点还存在,而c节点却被delete了。

这就要引出另一个问题了,如果在deleteNode前在使用c节点本身,那就可能引发不确定行为。

对题目的反思

由于ListNode是个单链表节点,而单链表节点本质上是无法做到在链表里删除自身的,所以这题只能通过这种替换的方式来伪造删除了节点。

这题会误导很多开发者,这题的设计模式更是不可取!

个人认为这题应该删除

203. 移除链表元素这题才是真正的移除链表元素!