模板(二)：访问容器中的元素

发表于

访问容器中的元素
保留Array和一个指向T的指针之间的密切关系要付出一定的代价

    1. 用户能够轻易得到一个指向Array内部的指针，即使Array本身不存在了，这个指针仍被保留
    1. 不得不暴露类的内部机制，一旦内存变化肯定导致用户错误；resize之类的扩展有诸多潜在错误

增加防止出错的中间层

模拟指针

1
2
3
4
5
6
7
8
9
10
11
template <class T> class Pointer {
public：
    Pointer(Array<T>& a, unsigned n = 0): ap(&a), sub(n) {}
    Pointer(): ap(0), sub(0) {}
    // Array<T> cann't be default: reference should bind a object
private:
    Array<T>* ap;
    unsigned sub;
    // ...
};
  • 复制一个Pointer之后，原Pointer和其副本都指向一个位置

获取元素

  • 最直接的方法会面临上述问题：
1
2
3
4
5
6
7
8
template <class T> class Pointer {
public:
    T& operator*() const {
        if (ap == 0)
            throw "* of unbound Pointer";
        return (*ap)[sub];
    }
};
  • 另一种解决方案会带来赋值不方便的新问题：
1
2
3
4
5
6
7
8
9
10
11
12
template <class T> class Pointer {
public:
    T operator*() const {
        if (ap == 0)
            throw "* of unbound Pointer";
        return (*ap)[sub];
    }
};
// "t = *p" is allowed but "*p = t" is forbidden
// the point is that it is hard to implement "*p = t"
// while "T* tp = &*p" is allowed
  • 引进update操作
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> class Pointer {
public：
    Pointer(Array<T>& a, unsigned n = 0): ap(&a), sub(n) {}
    Pointer(): ap(0), sub(0) {}
    
    T operator*() const {
        if (ap == 0)
            throw "* of unbound Pointer";
        return (*ap)[sub];
    }
    void update(const T& t) {
        if (ap == 0)
            throw "update of unbound Pointer";
        (*ap)[sub] = t;
    }
private:
    Array<T>* ap;
    unsigned sub;
    // ...
};
  • 相应地，Array类使用update操作，但会带来无法实现包含Array的Array的功能的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T> class Array {
public:
    T operator[](unsigned n) const {
        if (n >= sz)
            throw "Array suubscript out of range";
        return data[n];
    }
    void update(unsigned n, const T& t) {
        if (n >= sz)
            throw "Array subscript out of range";
        data[n] = t;
    }
};

方便性和安全性之间的权衡问题
选择何种方法取决于类会被确切地怎样使用

遗留问题

  • 如果Array不存在了还可能存在一个指向它的空悬Pointer

“软件工程基本定理”(though it isn’t a real theory): 通过引进一个额外的中间层能够解决任何问题。’

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
template <class T> class Array_data {
    friend class Array<T>;
    friend class Pointer<T>;
    Array_data(unsigned size = 0): data(new T[size]), sz(size), use(1) {}
    ~Array_data() { delete [] data; }
    const T& operator[](unsigned n) const {
        if (n >= sz)
            throw "Array subscript out of range";
        return data[n];
    }
    T& operator[](unsigned n) {
        if (n >= sz)
            throw "Array subscript out of range";
        return data[n];
    }
    // no implement that copy is no allowed
    Array_data(const Array_data&);
    Array_data& operator=(const Array_data&);
    T* data;
    unsigned sz;
    int use;
};
template <class T> class Array {
    friend class Pointer<T>;
public:
    Array(unsigned size): data(new Array_data<T>(size)) {}
    ~Array() {
        if (--data->use == 0)
            delete data;
    }
    const T& operator[](unsigned n) const {
        return (*data)[n];
    }
    T* operator[](unsigned n) {
        return (*data)[n];
    }
private:
    Array(const Array&);
    Array& operator=(const Array&);
    Array_data<T>* data;
};
template <class T> class Poiter: public Ptr_to_const<T> {
public:
    Pointer(Array<T>& a, unsigned n = 0): ap(a.data), sub(n) {
        ++ap->use;
    }
    Pointer(): ap(0), sub(0) {}
    Pointer(const Pointer<T>& p): ap(p.ap), sub(p.sub) {
        if (ap)
            ++ap->use;
    }
    ~Pointer() {
        if (ap && --ap->use == 0)
            delete ap;
    }
    Pointer& operator=(const Pointer<T>& p) {
        if (p.ap)
            ++p.ap->use;
        if (ap && --ap->use == 0)
            delete ap;
        ap = p.ap;
        sub = p.sub;
        return *this;
    }
    T& operator*() const {
        if (ap == 0)
            throw "* of unbound Ptr_to_const";
        return (*ap)[sub];
    }
private:
    Array_data<T>* ap;
    unsigned sub;
};
// the following code does work
Array<int>* ap = new Array<int>(10);
Pointer<int> p(*ap, 5);
delete ap;
*p = 42;

指向const Array的Pointer

  • 还无法使Pointer指向const Array的元素
    • const Array的实际对象很少，但通过引用传递Array参数(const Array&)时还是有用的

  • 定义独立的类，提供类型转换操作符给这个类，通过继承获得两种类型间的相似性

  • 类Pointer从Ptr_to_const继承而来，即使对象不是const类型也能把指针保存在Array_data中

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
template <class T> class Ptr_to_const {
public:
    // catch a argument const Array<T>& instead of Array<T>&
    Ptr_to_const(const Array<T>& a, unsigned n = 0): ap(a.data), sub(n) {
        ++ap->use;
    }
    Ptr_to_const(): ap(0), sub(0) {}
    Ptr_to_const(const Ptr_to_const<T>& p): ap(p.ap), sub(p.sub) {
        if (ap)
            ++ap->use;
    }
    ~Ptr_to_const() {
        if (ap && --ap->use == 0)
            delete ap;
    }
    Ptr_to_const& operator=(const Ptr_to_const<T>& p) {
        if (p.ap)
            ++p.ap->use;
        if (ap && --ap->use == 0)
            delete ap;
        ap = p.ap;
        sub = p.sub;
        return *this;
    }
    const T& operator*() const {
        if (ap == 0)
            throw "* of unbound Ptr_to_const";
        return (*ap)[sub];
    }
private:
    Array_data<T>* ap;
    unsigned sub;
};
// redefine class Pointer to keep something about constant
template <class T> class Poiter: public Ptr_to_const<T> {
public:
    Pointer(Array<T>& a, unsigned n = 0): Ptr_to_const<T>(a, n) {}
    Pointer() {}
    T& operator*() const {
        if (ap == 0)
            throw "* of unbound Ptr_to_const";
        return (*ap)[sub];
    }
};

增强操作

  • 重新设置Array大小
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
34
35
36
37
38
39
40
41
42
43
44
template <class T> class Array {
public:
    void resize(unsigned n) {
        // Array_data do the real operation
        data->resize(n);
    }
    //...
};
template <class T>
void Array_data<T>::resize(unsigned n) {
    if (n == sz) return ;
    T* odata = data;
    data = new T[n];
    copy(odata, sz > n ? n : sz);
    delete [] odata;
    sz = n;
}
template <class T>
void Array_data<T>::copy(T* arr, unsigned n) {
    for (int i = 0; i < n; ++i)
        data[i] = arr[i];
}
// another way of changing Array size
template <class T> class Array {
public:
    void reverse(unsigned new_sz) {
        if (new_sz >= data->sz)
            data->grow(new_sz);
    }
    //...
};
template <class T>
void Array_data<T>::grow(unsigned new_sz) {
    unsigned nsz = sz;
    if (nsz == 0)
        nsz = 1;
    whiel (nsz <= new_sz)
        nsz *= 2;
    resize(nsz);
}

  • 实现对Array的复制和赋值使包含Array的Array有效

  • 不允许对Array_data对象复制，故不定义operator=调用Array_data::operator=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T> class Array {
public:
    Array(const Array& a): data(new Array_data<T>(a.data->sz)) {
        data->copy(a.data->data, a.data->sz);
    }
    Array& operator=(const Array& a) {
        if (this != &a)
            data->clone(*a.data, a.data->data);
        return *this;
    }
    // ...
};
template <class T>
void Array_data<T>::clone(const Array_data& a, unsigned n) {
    delete [] data;
    data = new T[sz = a.sz];
    copy(a.data, sz);
}

尚未完全消除指针的需求

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