模板(四)：序列

发表于

容器类应该包含对象，而迭代器类的对象标识容器中的位置

  • Seq类: 精简指令集容器类，模仿纯Lisp中的列表(list)

技术状况

  • 类似: 数组包含若干值，辅助值(整数/指针)标识数组中某个位置
1
2
3
4
5
int a[N];
int i;
for (i = 0; i < N; i++)
    a[i] = i;

  • a作为容器，i作为迭代器

  • 容器可以使const类型的，需要两种迭代器:

    • 只能对容器进行读操作，T*
    • 既能对容器进行读操作又能进行写操作，const T*

传统观点

  • Lisp最初定义的列表:

  • nil: 没又元素的列表

  • cons(a, b): 列表中，第一个元素为a, 其后的元素为列表b中元素
  • car(s): s的第一个元素，s是至少有一个元素的列表
  • cdr(s): s的第一个元素之外的其他所有元素，s至少有一个元素的列表

  • null(s): 列表s没有元素则为真，否则为假

  • 使用C++的模板定义类Seq<T>

  • Seq<T>(): 创建并返回一个没有元素的列表

  • Seq<T>(t, s): 创建并返回一个序列(第一个元素为t、其后元素都是序列s中的元素)
  • s.hd(): 返回s的第一个元素，s至少有一个元素
  • s.tl(): 创建并返回一个序列(包含s中除了第一个元素外的所有其他元素，s至少有一个元素)
  • (bool)s: s没有元素则返回false，否则返回true
1
2
3
4
5
6
7
8
9
template<class T>
class Seq {
public:
    Seq();
    Seq(const T&, const Seq&);
    T hd() const;
    Seq tl() const;
    operator bool() const;
};
  • 避免复制Seq或者子序列，使Seq在合适的时候共享底层序列
  • 给元素一个引用计数
1
2
3
4
5
6
7
8
9
10
11
template<class T>
class Seq_item {
    friend class Seq<T>;
    int use;
    const T data;
    
    Seq_item* next;
    Seq_item(const T& t, Seq_item* s);
    Seq_item(const T& t): use(1), data(t), next(0) { }
};

技巧: 根据一个值或者一个已有的Seq创建一个新的Seq；之后两个Seq共享有s表示的尾链

  • 正确递增引用计数
1
2
3
4
5
template<class T>
Seq_item<T>::Seq_item(const T& t, Seq_item* s): use(1), data(t), next(s) {
    if (s) 
        s->use++;
}

采用引用计数，每次创建、销毁或者赋值给一个Seq对象时都需要处理
需要拷贝构造函数、析构函数和赋值操作符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
class Seq {
public:
    Seq();
    Seq(const T&, const Seq&);
    Seq(const Seq&);             // copy constructor
    ~Seq();                      // destructor
    Seq& operator=(const Seq&);  // assignment operator
    T hd() const;
    Seq tl() const;
    operator bool() const;
private:
    Seq_item<T>* item;           // basic element
};
  • 缺省(默认)构造函数
1
2
template<class T>
Seq<T>::Seq(): item(0) { }
  • 从一个指向T的引用和另一个Seq构造一个新的Seq
1
2
3
template<class T>
Seq<T>::Seq(const T& t, const Seq<T>& x):
    item(new Seq_item<T>(t, x.item)) { }
  • 布尔转型操作符
1
2
3
4
template<class T>
Seq<T>::operator bool() const {
    return item != 0;
}
  • 复制(拷贝)构造函数
1
2
3
4
5
template<class T>
Seq<T>::Seq(const Seq<T>& s): item(s.item) {
    if (item)
        item->use++;
}
  • hd操作返回第一个Seq_item中的值，序列为空时抛出异常
1
2
3
4
5
6
7
template<class T>
T Seq<T>::hd() const {
    if (item)
        return item->data;
    else
        throw "hd of an empty Seq";
}
  • 定义私有构造函数，实现tl
1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
Seq<T>::Seq(Seq_item<T>* s): item(s) {
    if (s)
        s->use++;
}
template<class T>
Seq<T> Seq<T>::tl() const {
    if (item)
        return Seq<T>(item->next);
    else
        throw "tl of an empty Seq";
}
  • 删除序列时，可以只删除共享尾链前的元素
  • 增加函数管理引用计数和在适当的时候删除Seq_item元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class T>
Seq<T>& Seq<T>::operator=(const Seq<T>& s) {
    if (s.item)
        s.item->use++; // 自我赋值的情况
    destroy(item);
    item = s.item;
    return *this;
}
template<class T>
Seq<T>::~Seq() {
    destroy(item);
}
template<class T>
Seq<T>::destroy(Seq_item<T>* item) {
    while (item && --item->use == 0) {
        Seq_item<T>* next = item->next;
        delete item;
        item = next;
    }
}

额外操作

  • Seq<T>(t, s): 显式声明类型T(未知类型)
1
2
3
4
template<class T>
Seq<T> cons(const T& t, const Seq<T>& s) {
    return Seq<T>(t, s);
}
  • 增加操作便于C++程序员使用
    • operator*(): hd()同义函数
    • operator++(): 简化赋值语句s = s.tl()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 前置operator++
template<class T>
Seq<T>& Seq<T>:operator++() {
    if (item) {
        Seq_item<T>* p = item->next;
        if (p)
            p->use++;
    }
}
// 后置operator++
template<class T>
Seq<T> Seq<T>::operator++(int ) {
    Seq<T> ret = *this;
    if (item) {
        --item->use;
        item = item->next;
        if (item)
            item->use++;
    }
    return ret;
}
template<class T>
T Seq<T>::operator*() {
    return hd();
}
  • 在列表头部放入新值
1
2
3
4
5
template<class T>
Seq<T>& Seq<T>::insert(const T& t) {
    item = new Seq_item(t, item);
    return *this;
}

使用范例

......

更多增加

  • 联接操作: operator+=, operator+

  • 对相等性(不等性)的检验

  • 增加length(长度)操作利于高效实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
bool operator==(const Seq<T>& op1, const Seq<T>& op2) {
    if (op1.length() != op2.length())
        return false;
    Seq_item<T> *p = op1.item;
    Seq_item<T> *q = op2.item;
    while (p != q) {
        assert(p != 0 && q != 0);
        if (*p++ != *q++)
            return false;
    }
    return true;
}
  • 在Seq对象中存储长度
1
2
3
4
5
6
7
8
9
10
11
template<class T>
class Seq {
public:
    unsigned length() {
        return len;
    }
private:
    unsigned len;
    // ...
};

  • 构造函数、赋值操作符、加法操作符、联接操作符、insert和tl函数都将被更新

  • 接受一个Seq_item的private构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
Seq<T>::Seq(Seq_item<T>* s, unsigned l): item(s), len(l) {
    if (s)
        s->use++;
}
template<class T>
Seq<T> Seq<T>::tl() const {
    if (item)
        return Seq<T>(item->next, len - 1);
    else 
        throw "tl of an empty Seq";
}

《C++沉思录(Cplusplus Thinking)》笔记