Published at:   |   Reading: 4106 words ~9min   |   PV/UV: /

模版链表

上周抽时间写了个模版链表，写完后发现编译过不了，开始我还以为是Xcode的问题，后来换成windows下发现还是不行，最后才知道，我把模版的具体实现和定义分离到.h和.cpp文件中，导致无法编译。具体原因我们等会儿再谈。

下面是实现的模版链表，由于上周后来参加数学建模就没有再写，排序函数还没写好。

  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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276

//
//  Chain.h
//  链表
//
//  Created by 欧 长坤 on 13-9-11.
//  Copyright (c) 2013年 欧 长坤. All rights reserved.
//

#ifndef ______Chain__
#define ______Chain__

#include

template  class Chain;

template
class ChainNode {

    friend class Chain;

private:

    T data;
    ChainNode *next;

};

template
class Chain {

private:

    ChainNode *head;

public:

    Chain(){head = NULL;}
    Chain(const Chain& copy);
    ~Chain();
    bool isEmpty() const {return (NULL == head);}
    int  lenth() const;
    bool find(int pos, T& value) const;
    int  search(const T& value) const;
    void output(std::ostream& out) const;
    //void erase();

    Chain& del(int pos, T& value);
    Chain& insert(int pos, const T& value);
    Chain& push_back(const T& value);
    Chain& pop_back(T& value);
    // 合并两个链表的函数（一个是完全拷贝，另一个是直接连接）

};

// 链表迭代器
// 使用方法：
// int *x;
// ChainIterator inter;
// x = inter.initialize(XXX);
// while (inter) {
//      cout << *x << ' ';
//      x = inter.next();
// }

template
class ChainIterator
{
private:

    ChainNode *location;

public:

    T* initialize(const Chain& list)
    {
        location = list.head;
        if (location)
            return &location->data;
        return 0;
    }
    T* next()
    {
        if (!location)
            return &location->data;
        return 0;
    }

};

// 实现
template
Chain::Chain(const Chain& copy)
{
    if (copy.isEmpty()) {
        head = NULL;
        return;
    }
    ChainNode *p = copy.head;
    head = new ChainNode;
    ChainNode *current = head;
    current->data = p->data;
    while (p->next) {
        current->next = new ChainNode;
        current = current->next;
        p = p->next;
        current->data = p->data;
    }
    current->next = NULL;
}

template
Chain::~Chain()
{
    ChainNode *p;
    while (NULL != head) {
        p = head->next;
        delete head;
        head = p;
    }
}

// 返回链表长度
template
int Chain::lenth() const
{
    ChainNode *current = head;
    int lenth = 0;
    while (current) {
        ++lenth;
        current = current->next;
    }
    return lenth;
}

// 查找链表中的第k个元素，并将其保存到value
// 如果不存在则返回false，否则true
template
bool Chain::find(int pos, T& value) const
{
    if(pos < 1)
        return false;
    ChainNode *current = head;
    int index = 1;  // current的索引
    while (indexnext;
        ++index;
    }
    if (current) {
        value = current->data;
        return true;
    }
    return false;
}

// 搜索value，如果发现value则返回value的索引
// 如果value不在链表中，则返回0
template
int Chain::search(const T& value) const
{
    ChainNode *current = head;
    int index = 1;  // current的索引
    while (current && current->data != value) {
        current = current->next;
        ++index;
    }
    if (current)
        return index;
    return 0;
}

// 使用迭代器可在线性时间内输出链表
// 将链表元素发送到输出流
template
void Chain::output(std::ostream &out) const
{
    ChainNode *current;
    for (current = head; current; current = current->next) {
        out << current->data << &quot; &quot;;
    }
}

// 重载<<
template
std::ostream& operator << (std::ostream& out, const Chain& value)
{
    value.output(out);
    return out;
}

// 把第pos的元素保存到value中，然后从链表中删除第pos个元素，pos从1开始
template
Chain& Chain::del(int pos, T &value)
{
    if (pos        throw &quot;Out of Bounds!&quot;;
    // p最终指向第pos个元素，并将其删除。
    ChainNode *p = head;
    if (1 == pos) {
        head = head->next;
    } else {
        ChainNode *q = head;
        for (int index = 1; index<(pos-1) && q; ++index) {             q = q->next;
        }
        if (!q || !q->next) {
            throw &quot;Out of Bounds!&quot;;
        }
        p = q->next;    // 存在第pos个元素
        q->next = p->next;  // 删除
    }
    // 保存第pos个元素并释放节点p
    value = p->data;
    delete p;
    return *this;
}

// n个元素共有n+1个空位，在第pos个元素插入value，pos从0开始
template
Chain& Chain::insert(int pos, const T &value)
{
    if (pos < 0) {
        throw &quot;Out of Bounds!&quot;;
    }
    // p最终将指向第pos个节点，并插入value
    ChainNode *p = head;
    for (int index = 1; indexnext;
    }
    if (pos>0 && !p) {
        throw &quot;Out of Bounds!&quot;;
    }
    ChainNode *temp = new ChainNode;
    temp->data = value;
    if (pos) {
        temp->next = p->next;
        p->next = temp;
    } else {
        temp->next = head;
        head = temp;
    }
    return *this;
}

template
Chain& Chain::push_back(const T& value)
{
    ChainNode *p = head;
    if (NULL == p) {
        p = new ChainNode;
        p->data = value;
        p->next = NULL;
        head = p;
        return *this;
    }
    while (p->next)
        p = p->next;
    p->next = new ChainNode;
    p = p->next;
    p->data = value;
    p->next = NULL;
    return *this;
}

template
Chain& Chain::pop_back(T& value)
{
    ChainNode *p = head;
    if (NULL == p) {
        value = 0;
        return *this;
    }
    while (p->next->next)
        p = p->next;
    value = p->next->data;
    delete p->next;
    p->next = NULL;
    return *this;
}

#endif /* defined(______Chain__) */

还有一点我很奇怪，“=”没有被重载难道可以让两个T类型的元素互相赋值吗？

1

p->data = value; // const T& value

模版分离编译

以下内容转自：http://blog.csdn.net/bichenggui/article/details/4207084 首先，一个编译单元（translation unit）是指一个.cpp文件以及它所#include的所有.h文件，.h文件里的代码将会被扩展到包含它的.cpp文件里，然后编译器编译该.cpp文件为一个.obj文件（假定我们的平台是win32），后者拥有PE（Portable Executable，即windows可执行文件）文件格式，并且本身包含的就已经是二进制码，但是不一定能够执行，因为并不保证其中一定有main函数。当编译器将一个工程里的所有.cpp文件以分离的方式编译完毕后，再由连接器（linker）进行连接成为一个.exe文件。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

//---------------test.h----------------//
void f();//这里声明一个函数f

//---------------test.cpp--------------//
#include &quot;test.h&quot;
void f()
{
     …//do something
}  //这里实现出test.h中声明的f函数

//---------------main.cpp--------------//
#include &quot;test.h&quot;
int main()
{
     f(); //调用f，f具有外部连接类型
}

在这个例子中，test. cpp和main.cpp各自被编译成不同的.obj文件（姑且命名为test.obj和main.obj），在main.cpp中，调用了f函数，然而当编译器编译main.cpp时，它所仅仅知道的只是main.cpp中所包含的test.h文件中的一个关于void f();的声明，所以，编译器将这里的f看作外部连接类型，即认为它的函数实现代码在另一个.obj文件中，本例也就是test.obj，也就是说，main.obj中实际没有关于f函数的哪怕一行二进制代码，而这些代码实际存在于test.cpp所编译成的test.obj中。在main.obj中对f的调用只会生成一行call指令，像这样：

1

call f [C++中这个名字当然是经过mangling[处理]过的]

在编译时，这个call指令显然是错误的，因为main.obj中并无一行f的实现代码。那怎么办呢？这就是连接器的任务，连接器负责在其它的.obj中（本例为test.obj）寻找f的实现代码，找到以后将call f这个指令的调用地址换成实际的f的函数进入点地址。需要注意的是：连接器实际上将工程里的.obj“连接”成了一个.exe文件，而它最关键的任务就是上面说的，寻找一个外部连接符号在另一个.obj中的地址，然后替换原来的“虚假”地址。

这个过程如果说的更深入就是：

call f这行指令其实并不是这样的，它实际上是所谓的stub，也就是一个jmp 0xABCDEF。这个地址可能是任意的，然而关键是这个地址上有一行指令来进行真正的call f动作。也就是说，这个.obj文件里面所有对f的调用都jmp向同一个地址，在后者那儿才真正”call”f。这样做的好处就是连接器修改地址时只要对后者的call XXX地址作改动就行了。但是，连接器是如何找到f的实际地址的呢（在本例中这处于test.obj中），因为.obj与.exe的格式是一样的，在这样的文件中有一个符号导入表和符号导出表（import table和export table）其中将所有符号和它们的地址关联起来。这样连接器只要在test.obj的符号导出表中寻找符号f（当然C++对f作了mangling）的地址就行了，然后作一些偏移量处理后（因为是将两个.obj文件合并，当然地址会有一定的偏移，这个连接器清楚）写入main.obj中的符号导入表中f所占有的那一项即可。

这就是大概的过程。其中关键就是：

编译main.cpp时，编译器不知道f的实现，所以当碰到对它的调用时只是给出一个指示，指示连接器应该为它寻找f的实现体。这也就是说main.obj中没有关于f的任何一行二进制代码。

编译test.cpp时，编译器找到了f的实现。于是乎f的实现（二进制代码）出现在test.obj里。

连接时，连接器在test.obj中找到f的实现代码（二进制）的地址（通过符号导出表）。然后将main.obj中悬而未决的call XXX地址改成f实际的地址。完成。

然而，对于模板，你知道，模板函数的代码其实并不能直接编译成二进制代码，其中要有一个“实例化”的过程。举个例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//----------main.cpp------
//
template
void f(T t)
{}
int main()
{
…//do something
f(10); // call f 编译器在这里决定给f一个f的实例
…//do other thing
}

也就是说，如果你在main.cpp文件中没有调用过f，f也就得不到实例化，从而main.obj中也就没有关于f的任意一行二进制代码！如果你这样调用了：

1
2

f(10); // f得以实例化出来
f(10.0); // f得以实例化出来

这样main.obj中也就有了f，f两个函数的二进制代码段。以此类推。 然而实例化要求编译器知道模板的定义，不是吗？ 看下面的例子（将模板的声明和实现分离）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


//-------------test.h----------------//
template
class A
{
public:
void f(); // 这里只是个声明
};

//---------------test.cpp-------------//
#include”test.h”
template
void A::f() // 模板的实现
{
…//do something
}

//---------------main.cpp---------------//
#include”test.h”
int main()
{
A a;
f(); // #1
}

编译器在#1处并不知道A::f的定义，因为它不在test.h里面，于是编译器只好寄希望于连接器，希望它能够在其他.obj里面找到A::f的实例，在本例中就是test.obj，然而，后者中真有A::f的二进制代码吗？NO！！！因为C++标准明确表示，当一个模板不被用到的时侯它就不该被实例化出来，test.cpp中用到了A::f了吗？没有！！所以实际上test.cpp编译出来的test.obj文件中关于A::f一行二进制代码也没有，于是连接器就傻眼了，只好给出一个连接错误。但是，如果在test.cpp中写一个函数，其中调用A::f，则编译器会将其实例化出来，因为在这个点上（test.cpp中），编译器知道模板的定义，所以能够实例化，于是，test.obj的符号导出表中就有了A::f这个符号的地址，于是连接器就能够完成任务。

关键是：在分离式编译的环境下，编译器编译某一个.cpp文件时并不知道另一个.cpp文件的存在，也不会去查找（当遇到未决符号时它会寄希望于连接器）。这种模式在没有模板的情况下运行良好，但遇到模板时就傻眼了，因为模板仅在需要的时候才会实例化出来，所以，当编译器只看到模板的声明时，它不能实例化该模板，只能创建一个具有外部连接的符号并期待连接器能够将符号的地址决议出来。然而当实现该模板的.cpp文件中没有用到模板的实例时，编译器懒得去实例化，所以，整个工程的.obj中就找不到一行模板实例的二进制代码，于是连接器也黔驴技穷了。

0%