求助，写的类链接失败

1210603696

我写了一个类 这是类声明：

1. #ifndef _NAME_SPACE_ZOUXIAOHANG_
   
2. #define _NAME_SPACE_ZOUXIAOHANG_
   
3. 
   
4. #include <iostream>
   
5. #include <iomanip>
   
6. #include <queue>
   
7. #include <assert.h>
   
8. 
   
9. template <class T>
   
10. class binary_search_tree
    
11. {
    
12. private:
    
13.         typedef struct node_t
    
14.         {
    
15.                 T value;
    
16.                 node_t *left;
    
17.                 node_t *right;
    
18.         } node, *tree;
    
19. public:
    
20.         typedef node *iterator;
    
21.         typedef const node *const_iterator;
    
22. private:
    
23.         //******
    
24.         tree m_root;
    
25.         size_t m_num;
    
26.         //******
    
27.         binary_search_tree(const binary_search_tree<T>& t);
    
28.         binary_search_tree& operator = (const binary_search_tree<T>& t);
    
29. 
    
30.         void _order(const tree t, const int ctrl);//ctrl: 0:pre_order 1:in_order 2:post_order
    
31.         void _display_tree(const_iterator p, int depth, int ctrl) const;//ctrl:0=root 1=left 2=right
    
32.         void _make_empty(iterator p);
    
33.         node* _find_node(iterator p, T x);
    
34.         node* _insert_node(iterator p, T x);
    
35.         node* _delete_node(iterator p, T x);
    
36. public:
    
37.         binary_search_tree():m_root(NULL), m_num(0){}
    
38.         ~binary_search_tree();
    
39. 
    
40.         iterator find_node(T x);
    
41.         iterator find_max();
    
42.         iterator find_min();
    
43.         bool insert_node(T x);
    
44.         iterator delete_node(T x);
    
45.         void make_empty();
    
46.         bool empty();
    
47.         size_t size();
    
48.         void pre_order();
    
49.         void in_order();
    
50.         void post_order();
    
51.         void level_order();
    
52.         const_iterator root();
    
53.         void display_tree() const;//ctrl:0=root 1=left 2=right
    
54.         void display_tree();//ctrl:0=root 1=left 2=right
    
55. };
    
56. 
    
57. template <class T>
    
58. std::ostream& operator<<(std::ostream& os, const binary_search_tree<T>& t);
    
59. 
    
60. #endif
    

复制代码

下面是实现文件：

1. #include "./binary_search_tree.h"
   
2. 
   
3. template <class T>
   
4. void binary_search_tree<T>::_order(const tree t, const int ctrl)//ctrl: 0:pre_order 1:in_order 2:post_order
   
5. {
   
6.         if(0 == ctrl)
   
7.         {
   
8.                 if(NULL != t)
   
9.                 {
   
10.                         std::cout<<t->value<<" ";
    
11.                         _order(t->left, 0);
    
12.                         _order(t->right, 0);
    
13.                 }
    
14.         }
    
15.         else if(1 == ctrl)
    
16.         {
    
17.                 if(NULL != t)
    
18.                 {
    
19.                         _order(t->left, 1);
    
20.                         std::cout<<t->value<<" ";
    
21.                         _order(t->right, 1);
    
22.                 }
    
23.         }
    
24.         else if(2 == ctrl)
    
25.         {
    
26.                 if(NULL != t)
    
27.                 {
    
28.                         _order(t->left, 2);
    
29.                         _order(t->right, 2);
    
30.                         std::cout<<t->value<<" ";
    
31.                 }
    
32.         }
    
33. }
    
34. template <class T>
    
35. void binary_search_tree<T>::_display_tree(const_iterator p, int depth, int ctrl) const//ctrl:0=root 1=left 2=right
    
36. {
    
37.         if(NULL == p)
    
38.                 return ;
    
39.         std::cout<<std::setw(depth);
    
40.         if(0 == ctrl)
    
41.                 std::cout<<"root:";
    
42.         else if(1 == ctrl)
    
43.                 std::cout<<"left";
    
44.         else if(2 == ctrl)
    
45.                 std::cout<<"right";
    
46.         std::cout<<p->value<<std::endl;
    
47.         _display_tree(p->left, depth+6, 1);
    
48.         _display_tree(p->right, depth+6, 2);
    
49. }
    
50. template <class T>
    
51. void binary_search_tree<T>::_make_empty(iterator p)
    
52. {
    
53.         if(NULL != p)
    
54.         {
    
55.                 _make_empty(p->left);
    
56.                 _make_empty(p->right);
    
57.                 delete p;
    
58.         }
    
59. }
    
60. template <class T>
    
61. typename binary_search_tree<T>::iterator binary_search_tree<T>::_insert_node(iterator p, T x)
    
62. {
    
63.         if(NULL == p)
    
64.         {
    
65.                 p = new        node;
    
66.                 assert(NULL != p);
    
67.                 p->value = x;
    
68.                 p->left = p->right = NULL;
    
69.                 ++m_num;
    
70.         }
    
71.         else if(x < p->value)
    
72.                 p->left = _insert_node(p->left, x);
    
73.         else if(x > p->value)
    
74.                 p->right = _insert_node(p->right, x);
    
75. 
    
76.         return p;
    
77. }
    
78. template <class T>
    
79. typename binary_search_tree<T>::iterator binary_search_tree<T>::_delete_node(iterator p, T x)
    
80. {
    
81.         if(NULL == p)
    
82.                 return NULL;
    
83.         if(x < p->value)
    
84.                 p->left = _delete_node(p->left, x);
    
85.         else if(x > p->value)
    
86.                 p->right = _delete_node(p->right, x);
    
87.         else
    
88.         {
    
89.                 iterator tmp = NULL;
    
90.                 if(p->left && p->right)// p has two childs
    
91.                 {
    
92.                         tmp = m_root;
    
93.                         m_root = p->right;
    
94.                         p->value = find_min()->value;
    
95.                         m_root = tmp;
    
96.                         p->right = _delete_node(p->right, p->value);
    
97.                 }
    
98.                 else
    
99.                 {
    
100.                         tmp = p;
     
101.                         if(!p->left)
     
102.                                 p = p->right;
     
103.                         else if(!p->right)
     
104.                                 p = p->left;
     
105.                         delete tmp;
     
106.                         --m_num;
     
107.                 }
     
108.         }
     
109.         return p;
     
110. }
     
111. template <class T>
     
112. typename binary_search_tree<T>::iterator binary_search_tree<T>::_find_node(iterator p, T x)
     
113. {
     
114.         if(NULL == p)
     
115.                 return NULL;
     
116.         if(x < p->value)
     
117.                 return _find_node(p->left, x);
     
118.         else if(x > p->value)
     
119.                 return _find_node(p->right, x);
     
120.         else
     
121.                 return p;
     
122. }
     
123. 
     
124. template <class T>
     
125. binary_search_tree<T>::~binary_search_tree()
     
126. {
     
127.         make_empty();
     
128. }
     
129. template <class T>
     
130. typename binary_search_tree<T>::iterator binary_search_tree<T>::find_node(T x)
     
131. {
     
132.         return _find_node(m_root, x);
     
133. }
     
134. template <class T>
     
135. typename binary_search_tree<T>::iterator binary_search_tree<T>::find_max()
     
136. {
     
137.         node *p = m_root;
     
138.         while(NULL != p && NULL != p->right)
     
139.                 p = p->right;
     
140.         return p;
     
141. }
     
142. template <class T>
     
143. typename binary_search_tree<T>::iterator binary_search_tree<T>::find_min()
     
144. {
     
145.         node *p = m_root;
     
146.         while(NULL != p && NULL != p->left)
     
147.                 p = p->left;
     
148.         return p;
     
149. }
     
150. template <class T>
     
151. bool binary_search_tree<T>::insert_node(T x)
     
152. {
     
153.         return (m_root = _insert_node(m_root, x)) == NULL ? false : true;
     
154. }
     
155. template <class T>
     
156. typename binary_search_tree<T>::iterator binary_search_tree<T>::delete_node(T x)
     
157. {
     
158.         return _delete_node(m_root, x);
     
159. }
     
160. template <class T>
     
161. void binary_search_tree<T>::make_empty()
     
162. {
     
163.         _make_empty(m_root);
     
164.         m_root = NULL;
     
165.         m_num = 0;
     
166. }
     
167. template <class T>
     
168. bool binary_search_tree<T>::empty()
     
169. {
     
170.         return m_num == 0;
     
171. }
     
172. template <class T>
     
173. size_t binary_search_tree<T>::size()
     
174. {
     
175.         return m_num;
     
176. }
     
177. template <class T>
     
178. void binary_search_tree<T>::pre_order()
     
179. {
     
180.         if(NULL != m_root)
     
181.                 _order(m_root, 0);
     
182. }
     
183. template <class T>
     
184. void binary_search_tree<T>::in_order()
     
185. {
     
186.         if(NULL != m_root)
     
187.                 _order(m_root, 1);
     
188. }
     
189. template <class T>
     
190. void binary_search_tree<T>::post_order()
     
191. {
     
192.         if(NULL != m_root)
     
193.                 _order(m_root, 2);
     
194. }
     
195. template <class T>
     
196. void binary_search_tree<T>::level_order()
     
197. {
     
198.         if(NULL == m_root)
     
199.                 return ;
     
200.         iterator p = m_root;
     
201.         std::queue<node*> q;
     
202.         q.push(p);
     
203.         while(!q.empty())
     
204.         {
     
205.                 p = q.front();
     
206.                 std::cout<<p->value<<" ";
     
207.                 if(NULL != p->left)
     
208.                         q.push(p->left);
     
209.                 if(NULL != p->right)
     
210.                         q.push(p->right);
     
211.                 q.pop();
     
212.         }
     
213. }
     
214. template <class T>
     
215. typename binary_search_tree<T>::const_iterator binary_search_tree<T>::root()
     
216. {
     
217.         return m_root;
     
218. }
     
219. template <class T>
     
220. void binary_search_tree<T>::display_tree() const
     
221. {
     
222.         _display_tree(m_root, 2, 0);
     
223. }
     
224. template <class T>
     
225. void binary_search_tree<T>::display_tree()
     
226. {
     
227.         _display_tree(m_root, 2, 0);
     
228. }
     
229. 
     
230. 
     
231. template <class T>
     
232. std::ostream& operator<<(std::ostream& os, const binary_search_tree<T>& t)
     
233. {
     
234.         t.display_tree();
     
235.         return os;
     
236. }
     

复制代码

我写了一个例程来测试我的binary_tree:

1. #include "binary_search_tree.h"
   
2. 
   
3. int main(int argc, char const *argv[])
   
4. {
   
5.         binary_search_tree<int> t;
   
6.         binary_search_tree<int>::iterator it;
   
7.     t.make_empty();
   
8.     t.insert_node(10);
   
9.         return 0;
   
10. }

复制代码

我编译链接的时候codeblock给出了下面错误：
obj\Debug\main.o||In function `main'
C:\Users\zxh\Desktop\test\main.cpp|7|undefined reference to `binary_search_tree<int>::make_empty()'|
C:\Users\zxh\Desktop\test\main.cpp|8|undefined reference to `binary_search_tree<int>::insert_node(int)'|
C:\Users\zxh\Desktop\test\main.cpp|9|undefined reference to `binary_search_tree<int>::~binary_search_tree()'|
C:\Users\zxh\Desktop\test\main.cpp|9|undefined reference to `binary_search_tree<int>::~binary_search_tree()'|
||=== Build finished: 4 errors, 0 warnings ===|

我找了很久实在是不知道为什么会链接失败，我明明生成了binary_tree.o并链接进来了啊，在ubuntu下g++ binary_tree.o main.c -o main也提示同样的问题

1210603696

把测试例程写在binary_tree.cpp下是可以成功运行的

linux_c_py_php

模板不支持分离编译啊

1210603696

不可能不支持啊，你把我的代码编译链接一下看看是不是也是失败回复 3# linux_c_py_php


   

myworkstation

回复 2# 1210603696

通常模板的定义也应该放在头文件中实现，你在binary_tree.cpp中调用成功是因为模板的定义和调用都在一个translate unit中。引发这个问题的原因是模板的“两阶段查找”造成的。具体的说是在第二个阶段进行模板实例化时产生的。当实例化模板时（在实例化点POI)相应模板定义必须是可见的。如果调用模板的代码位同binary_tree.cpp，在你的代码中恰好满足在一个translate unit中模板的定义可见，所以没有问题，但如果调用模板的代码在另一个文件中就会找不到模板的定义所以出错了。把模板声明和定义放在一个文件中既所谓的“包含模型”，虽然C++标准也说明了可把把模板定义放到cpp中，既所谓的“分离模型”，但要求显示使用export关健字，而且很多编译器都支持的不好，所以“包含模型”是实际的标准。
   

1210603696

回复 5# myworkstation
那难道项目中都要将模版实现放在.h文件里？


   

1210603696

回复 5# myworkstation
嗯！我把模版的实现放在了.h文件里，程序能运行了，谢谢了

   

myworkstation

回复 6# 1210603696

通常来讲是这样子的，你可以看看stl基本上都是这么干的。
   

Aquester

linux_c_py_php 发表于 2013-08-21 21:26
模板不支持分离编译啊

倒没说不支持，主要是编译链接时能看到相应的实现，C++标准有个export关键字修改类定义，用来支持模板分离编译模式，不过很多编译器可能不支持export关键词。