|
近来突发奇想，用智能指针来实现基本的数据结构会怎么样？比如，链表、二叉树等。
如果真有这样奇妙的配合，为何以前好像从来没听说过呢？是孤陋寡闻了吗？ 不如自己实现一个试试看。看会出现些什么问题。
链表好像比树要简单。那么用智能指针实现链表会怎么样呢？ 先挑战一下循环双向链表。
第一个问题是，选什么智能指针。
可选的自然只有3种： unique_ptr, shared_ptr, weak_ptr. weak_ptr 是辅助 shared_ptr 的，可以不算；那么就只有2种了。
选 shared_ptr 似乎会有潜在的循环引用问题，而且在这个例子里并不是 weak_ptr 可以解决的，比如： A -> B -> C -> A ，全都用next指针，所以没处换 weak_ptr.
那么选 unique_ptr 呢？ 更有问题。因为双向链表有 next 指针和 prev 指针。如果这2个指针都是 unique_ptr , 那么就会造成同一个节点，它既是前一个节点的next，又是后一个节点的prev，而这2个指针又都是 unique_ptr , 这就有问题了。如果其中一个释放了，而另一个没有释放且继续使用，那就出错了； 或者2个都释放，也会造成程序崩溃。
怎么办呢？ 将 next 指针设为 unique_ptr, 而 prev 指针仍使用 raw 指针。
个人感觉这是一种 ugly 的做法，这就是第1个问题了： next指针都用unique_ptr保护了，而prev指针又没有用智能指针保护。
但是，假设就这么实现。很快，我们遇到了第2个问题： next指针是unique_ptr，那么最后一个节点的next指针指向的是head，这怎么赋值？
我们会发现很难赋值，可能就没有办法赋值。大致代码如下：
unique_ptr<Node> node(new int(10));
node->prev = head->prev;
head->prev = node.get();
node->prev->next = std::move(node);
node->next = std::move(head);
以上代码有一个问题，最后这句 std::move(head) 其实没办法做。 head是这个List类的一个成员变量，用来做各种基本操作（如push_back，push_front, front, back 等）的，所以不能给move了。
不过这第2个问题有一个非常巧妙又简单的解决办法，就是最后节点的next指针不用指向head，只要设为空即可。理由是，因为反正最后一个节点可以通过 head->prev 找到，我们就可以不再设置它的next.
但是很快，我们又发现了第3个问题： 这个链表没法遍历。
笔者没有设想过用 iterator 来实现的情况。只是简单设想了通过head指针来从前往后遍历。
这基本无法做到。因为head基本无法暴露出去，即使把head暴露出去，它也是个unique_ptr，不move的话，就没有办法给别人使用；如果直接用get(),那又何必把它设为 unique_ptr 呢？
但是我们发现，其实可以从后往前遍历。可是这又是因为从后往前使用的prev指针，即原生指针。这似乎有点嘲讽了。
一个没法遍历的链表有什么用呢？ 其实也有点用。就是用来实现一个Queue其实还是可以的。
说了这么多，那么这个链表中使用 unique_ptr 的好处到底在哪里呢？
有一个好处。就是你不用去写这个List类的析构函数啦。 head节点析构的时候，它发现它的next成员变量是一个unique_ptr, 于是就去析构next； 于是就这么一直递归下去，最后导致整个链表被析构。
好像也就这么一个好处。
不过这个好处有没有带来什么坏处呢？
不好意思，又带来了一个坏处。这就是第4个问题 - 递归层数过多会引起爆栈。
在笔者下面的程序中，如果链表节点的个数超过65500左右，就会爆栈了。
除了以上4个问题，还有第5个问题 - 增加了代码的复杂度，较容易出错。
分析了这么多，笔者个人最终的结论就是，最好不要使用智能指针来实现基本的数据结构，会引起很多不必要的麻烦。
这可能是因为基本数据结构都是串联起来的一个庞大的组织性质的存在；而不像普通的对象大多数时候都是独立的存在。
智能指针主要目的是为了加强内存管理、防止内存泄漏，但是当它处于一个庞大复杂的组织中时，似乎就会影响到这个组织的种种行为；或许它只是适用于相对独立存在的对象。
最后，笔者给出用unique_ptr和原生指针共同实现的循环双向链表及其测试程序如下。
为了简单起见，程序中禁用了拷贝构造和赋值操作符。
而在测试程序中，如果你将链表节点个数改得比较多（在笔者的机器上是超过65500），就会发现程序崩溃。
代码如下：
- list.hpp
#ifndef LIST_HPP
#define LIST_HPP
#include <memory>
#include <iostream>
namespace finix {
template <typename T>
class List {
private:
struct Node {
T data;
std::unique_ptr<Node> next;
Node * prev;
Node() {
next = std::unique_ptr<Node>();
prev = nullptr;
}
Node(T d) : data(d), next(std::unique_ptr<Node>()), prev(nullptr) {}
~Node() {
std::cout << "Destructing Node: data = " << data << std::endl;
}
};
private:
std::unique_ptr<Node> head;
public:
List<T>() : head(std::unique_ptr<Node>(new Node)) {
head -> prev = head.get();
}
List<T>(const List<T>& other) = delete;
List<T>(List<T>&& other) = delete;
List<T>& operator = (const List<T> & other) = delete;
List<T>& operator = (List<T> && other) = delete;
virtual ~List<T>() {}
bool empty() {
return head -> prev == head.get();
}
void push_back(T d) {
std::unique_ptr<Node> ptr = std::unique_ptr<Node>(new Node(d));
ptr->prev = head->prev;
head->prev = ptr.get();
ptr->prev->next = std::move(ptr);
}
void push_front(T d) {
std::unique_ptr<Node> node(new Node(d));
if (empty()) {
head->next = std::move(node);
head->next->prev = head.get();
head->prev = head->next.get();
}
else {
head->next->prev = node.get();
node->next = std::move(head->next);
node->prev = head.get();
head->next = std::move(node);
}
}
void pop_front() {
if (empty()) return;
std::unique_ptr<Node> tmp = std::move(head->next);
head -> next = std::move(tmp->next);
if (head->next) {
head->next->prev = head.get();
}
else {
head->prev = head.get();
}
}
void pop_back() {
if (empty()) return;
Node * tmp = head->prev;
head->prev = tmp->prev;
head->prev->next.reset();
}
T& front() {
return head->next->data;
}
T& back() {
return head->prev->data;
}
};
}
#endif
- test_list.cpp
#include <iostream>
#include "list.hpp"
using namespace std;
using namespace finix;
int main()
{
List<int> mylist;
for (int i=0; i<10; i++) {
mylist.push_back(i+1);
}
cout << "Done..." << endl;
return 0;
}
（完）
|