技术现状
前面我们通过迭代器和容器类的方式建立了c++容器的常规范例。迭代器的思路很适合传统的数据结构，但是在实践过程中，我们需要为每一种容器都提供两种类型的迭代器：Iterator<T>和Const_iterator<T>。另外，我们还需要通过重写操作符的方式为两个迭代器提供各种组合的方式，而且有的操作符还需要分别在两个迭代器类中实现。
基本的传统观点
参考Lisp提供的容器列表，我们可以汇总出列表需要提供的能力：
- nil-空列表
- cons(a,b)-将数据a和列表b组合成新的列表。且第一个元素为a，后续元素为b中的元素。
- car(s)-返回s的第一个元素，s必须为列表。
- cdr(s)-返回s中除第一个元素以外的所有其他元素。
- null(s)-如果s中无数据则为true；否则返回false。
通过这些基本操作Lisp已经可以提供非常强大功能了。如果我们加上一限制条件：所有的元素都是同一类型的，c++也可以实现这种列表的容器。
假设我们实现的容器叫做Seq（序列）
则根据Lisp提供的功能，我们可以写出如下声明：
template <class T>
class Seq
{
public:
Seq();
Seq(const T&, const Seq<T>&);
Seq(const Seq<T>&);
~Seq();
Seq& operator=(const Seq<T>&);
T hd() const ;
Seq<T> tl() const ;
operator bool() const;
};
同样我们来考虑私有成员应该是什么。
我们可以使用链表来描述这个Seq，所以私有成员肯定是一个指向链表头节点的指针。所以我们需要先定义这个链表的结构。同时我们可能不需要每个Seq都单独的持有完整的链表，多个Seq可能可以共享一些链表的区域，所以我们的链表结构需要采用引用计数的方式进行处理。
由上我们可以得到链表的结构定义：
template <class T>
class Seq_item
{
friend class Seq<T>; // 因为Seq类需要处理引用计数的问题，所以设置为友元
int use;
T data;
Seq_item* next;
Seq_item(const T& t):data(t), use(1), next(nullptr) {}
Seq_item(const T& t, Seq_item* s): data(t),use(1),next(s) {
// 这里不使用while循环更新引用计数是说明从s开始到最后都是共享的。
if (s != nullptr) {
s->use++;
}
}
};
现在我们可以给出Seq的完整声明了：
template <class T>
class Seq
{
public:
Seq();
Seq(const T&, const Seq<T>&);
Seq(const Seq<T>&);
~Seq();
Seq& operator=(const Seq<T>&);
T hd() const ;
Seq<T> tl() const ;
operator bool() const;
private:
Seq_item<T>* item;
};
下面我们来实现这个类。
- 我们允许了默认构造函数的存在，因为我们不想放弃可以定义
Seq<T> array_s[10];的性质。考虑默认构造函数应该是一个空的Seq，所以默认构造函数定义为：
template<class T>
Seq<T>::Seq(): item(nullptr) {}
- 带参数的构造函数应该是通过
T& t和Seq<T>& s构建一个新的Seq，这个新的Seq的item为新链表的头。同时要指明除了第一个元素以外，其他元素都是共享的，所以要修改s的引用计数，这一步骤可以通过Seq_item的构造函数实现。
template<class T>
Seq<T>::Seq(const T & t, const Seq<T>& other):item( new Seq_item<T>(t, other.item)) {}
- 拷贝构造函数要处理item的引用计数问题。我们必须在item被赋值以后，增加他的引用计数，来表示整个链表都是共享的。
template<class T>
Seq<T>::Seq(const Seq<T> &other):item(other.item) {
if (item != nullptr) {
item->use++;
}
}
- bool类型的转换很容易实现：
template<class T>
Seq<T>::operator bool() const {
return item != nullptr;
}
- 析构函数需要保证只释放掉自己持有的链表节点，所以我们需要遍历整个链表，减小每个节点的引用计数，同时判断如果引用计数已经为0则释放节点。
template<class T>
Seq<T>::~Seq() {
destory(item);
}
template<class T>
void Seq<T>::destory(Seq_item<T> *it) {
while(it != nullptr && --it->use == 0) {
Seq_item<T>* temp = it->next;
delete it;
it = temp;
}
}
- 赋值运算符需要保证自己赋值给自己的时候不会出现先删除的情况，所以我们先将引用计数+1
template<class T>
Seq<T>& Seq<T>::operator=(const Seq<T> &other) {
if (other.item != nullptr) {
other.item->use++;
}
destory(item);
item = other.item;
return *this;
}
- hd()的实现只需要注意Seq不能为空的就行
template<class T>
T Seq<T>::hd() const {
if (item != nullptr) {
return item->data;
}
else {
throw "hd of an empty Seq";
}
}
- tl()的实现我们需要返回一个新的Seq，这个Seq由
item->next构造，所以Seq类需要新增一个构造函数Seq(Seq_item<T>* s)
template<class T>
Seq<T> Seq<T>::tl() const {
if (item != nullptr) {
return Seq<T>(item->next);
}
else {
throw "tl of an empty Seq";
}
}
template<class T>
Seq<T>::Seq(Seq_item<T> *s): item(s) {
if (s != nullptr) {
item->use++;
}
}
至此我们已经实现了具备Lisp列表功能的容器Seq。但是对于Lisp描述的cons功能我们采用了构造函数Seq(const T&, const Seq<T>& s)来实现的。使用这个构造函数我们必须指定T是什么，例如：Seq<int> s(10,s0)或者Seq<int>* p = new Seq<int>(10,s)。但是我们不是所有的时候都是知道T的类型的，所以需要为其提供一个函数模版处理：
template <class T>
Seq<T> cons(const T& t, const Seq<T>& s) {
return Seq<T>(t, s);
}
另外，我们没有提供一个成员length来记录Seq的长度，所以我们需要提供一个函数模版来方便用户获取长度。
// 递归
template <class T>
int length(const Seq<T>& s) {
// 这里是隐式转换为bool类型 operator bool()
if (s) {
return 1 + length(s.tl());
}
return 0;
}
// 迭代使用副本操作
template <class T>
int length(Seq<T> s) {
int len = 0;
while (s) {
s = s.tl();
len++;
}
return len;
}
对于普遍的C++程序员而言，使用s = s.tl();使其指向下一个总归是不如s++;更符合习惯。同样使用s.hd();是不如使用*s来获取值符合习惯。所以我们新增这两个运算符的操作。
template<class T>
T Seq<T>::operator*() {
return hd(); // 这里直接使用hd()成员函数就行了，语义是一样的。
}
// 前置自增
template<class T>
Seq<T> &Seq<T>::operator++() {
if (item != nullptr) {
Seq_item<T>* p = item->next;
if (p != nullptr && p->use == 1) {
p->use++; // 表明从这里开始是共享的序列
}
if (--item->use == 0) { // 没人使用的时候清理掉
delete item;
}
item = p;
}
return *this;
}
template<class T>
Seq<T> Seq<T>::operator++(int) {
Seq<T> temp = *this; // 这里使用了operator=导致item的引用计数会增加
if (item != nullptr) {
--item->use; // 所以这里直接--是没有问题的。
item = item->next;
if (item != nullptr && item->use == 1) { // 到达了共享序列
item->use++;
}
}
return temp;
}
使用这个类
我们感觉已经为Seq提供了足够的方法，现在是时候使用这个类了。
- 合并两个Seq
template <class T>
Seq<T> merge(const Seq<T>& x, const Seq<T>& y) {
if (!x)
return y;
if (!y)
return x;
T xh = x.hd();
T yh = y.hd();
if (xh < yh) {
return cons(xh, merge(x.tl(), y));
}
return cons(yh, merge(x, y.tl()));
}
- 将一个Seq分裂为两个Seq
// 分为两堆
template <class T>
void split(Seq<T> origin, Seq<T>& y, Seq<T>& z) {
while(origin) {
y.insert(origin.hd());
if (++origin) {
z.insert(origin.hd());
++origin;
}
}
}
- 你肯定猜到了，下面就是进行归并排序了
// 归并排序 O(nlogn)
template <class T>
Seq<T> sort(const Seq<T> x) {
if (!x || !x.tl()) {
return x;
}
Seq<T> p, q;
split(x, p, q);
return merge(sort(p), sort(q));
}
- 通常的容器都允许一个reverse的操作，同样的我们的Seq也来一个吧
template<class T>
Seq<T>& Seq<T>::reverse() {
if (item != nullptr) {
Seq_item<T>* tail = nullptr;
Seq_item<T>* curr = item;
Seq_item<T>* previous = nullptr;
do {
Seq_item<T>* next = curr->next;
curr->next = previous;
previous = curr;
curr = next;
}while(curr != nullptr);
tail = previous;
item = tail;
}
return *this;
}
但是这样的写法是错误的，因为如果要进行reverse操作，则必须保证Seq获取到了全部的Seq_item的所有权。所以我们还需要一个将共享链变为uniq的方法：
template<class T>
Seq_item<T> *Seq<T>::own_tail() {
if (item == nullptr) {
return item;
}
Seq_item<T>* i = item;
Seq_item<T>** p = &item;
while(i->use == 1) {
if (i->next == nullptr) { // 遍历到终点都是自己持有的，返回最后一个节点。
return i;
}
p = &i->next;
i = i->next;
}
// 已经到达了共享链开头
*p = new Seq_item<T>(i->data);
--i->use;
i = i->next;
Seq_item<T>* j = *p;
while(i != nullptr){
j->next = new Seq_item<T>(i->data);
i = i->next;
j = j->next;
}
return j;
}
// 修改后的reverse
template<class T>
Seq<T>& Seq<T>::reverse() {
if (item != nullptr) {
Seq_item<T>* tail = own_tail();
Seq_item<T>* curr = item;
Seq_item<T>* previous = nullptr;
do {
Seq_item<T>* next = curr->next;
curr->next = previous;
previous = curr;
curr = next;
}while(curr != nullptr);
item = tail;
}
return *this;
}
除了这些常规操作以外，可能我们还需要提供比较操作符等。
这里就不详细写了。
总结
- 使用Seq这种方式我们不需要提供两个Iterator类来操作这个容器。
- 该Seq类仅依靠我们实现的功能就能满足大量的操作需求了。而且可以满足函数式编程的编程范式。
