模板(一)：设计容器类

发表于

容器类设计

容器：保存值的集合的数据结构

  • 语言内建容器：数组、结构体
  • C++没有提供更多的内建容器：不将容器的设计限定到某种单一的方法上(可能不存在唯一正确的方法)

  • 容器包含对象

  • 复制容器意味复制存储在容器中的值(而不是容器本身)

  • 函数传参数方式 void f(const Container<T>&) 避免大对象的复制

  • 区分读和写

    • operator[]只用于取数
    • 用成员函数update(i, x)修改索引为i的元素为x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class T> class Container {
    // ...
public:
    T operator[](Index) const;
    void update(Index, const T&);
    // ...
};
Container< Container<int> >c;
Index i, j;
int k = c[i][j];
// only way to modify the element in Container
// c[i][j]
void update(Index, const T&);
void update(Index, Index, const T&);
// hard to deal with much more dimension
// c[i] return type T instead of T&
// c[i].update(j, new_value) does not work

  • 获取容器的元素严格分清类型T(作右值)和类型T&(作左值)

  • 容器增长：按区块(chunk)增加容器大小的分配策略

  • 容器操作

    • 容器数组：必须有缺省构造函数
    • “顺序地”遍历容器中所有元素：先给元素强制规定顺序(解决方案：迭代器(iterator))

  • 容器元素的类型

    1. 类型为T的元素可以进行行为正确的复制、赋值和销毁
    • T::T(const T&)
    1. 可以判定两个元素是否相等
    • operator==(const T&, cosnt T&)
    1. 为增加性能，有关于偏序关系或全序关系的定义(如set)
    • operator<(const T&, const T&)
    1. 考虑是否重载 operator<<(ostream&, const Container<T>&)
    • 兼顾不使用标准输入输出操作库或不用输入输出操作的用户，提供遍历整个容器的机制

  • 容器不可通过继承关联起来

1
2
3
4
5
6
7
// if Container<Airplane> is derived from Container<Vehicle>
Vehicle v;
Container<Airplane> ca;
Container<Vehicle>& vp = ca;
vp.insert(v);
// that does not make any sence

实例 : an array-like class

  • 使用指针和使用下标的差别
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// by index
int i;
for (i = 0; i < N; ++i)
    f(x[i]);
// by pointer
T* p;
for (p = x; p < x + N; ++p)
    f(*p);
// a simplified version
T* p;
while (p < x + N)
    f(*p++);

  • 区别：

    1. 下标值本身就有意义，与是否用作下标无关
    • 通过下标进行元素访问的程序要另外知道正在使用的数组(才能访问整个数组)
    1. 要访问容器的元素没必要知道容器的标识，指针本身就包含所有的必要信息
    • 程序只要拥有一个指向数组元素的指针就能访问整个数组

这些区别影响设计，比”下标易于理解，指针效率高”的区别更为重要

  • 禁止(数组)复制和赋值

  • 使用operator[]存取元素

  • 关于扩展：定长

  • 缺省构造函数：可以创建包含数组的数组

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
28
29
30
31
32
33
template<class T>
class Array {
public:
    Array(): data(0), sz(0) {}
    Array(unsigned size): sz(size), data(new T(size)) {}
    ~Array() { delete [] data; }
    const T& operator[](unsigned n) const {
        if (n >= sz || data == 0)
            throw "Array subscript out of range";
        return data[n];
    }
    T& operator[](unsigned n) {
        if (n >= sz || data == 0)
            throw "Array subscript out of range";
        return data[n];
    }
    operator const T*() const {
        return data;
    }
    operator T*() {
        return data;
    }
private:
    T* data;
    unsigned sz;
    Array(const Array* a);
    Array& operator=(const Array&);
};

缺陷

    1. (也存在于内建数组中)包含元素的Array消失后，它的元素地址还在
1
2
3
4
5
6
7
8
void f() {
    int *p;
    {
        Array<int> x(20);
        p = &x[10];
    }
    cout << *p; // no exist
}
    1. 允许用户访问它的元素地址，透露太多内部运作的信息，违背了封装理念
    • 允许Array被构造后改变长度会导致旧指针失效

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