vector的实现以及模板类的接口与实现分离问题

今天最大的收获就是把实现这个vector模板类,虽然花费了5个小时左右,但是期间学到的知识实在是太值得了!
这个模板类是来至《数据结构与算法分析–C++描述》 ,Weiss写的,很好的一本书,不过这本书不是针对数据结构初学者的,也不是针对C++初学者的,数据结构入门还是严蔚敏老师的好。
首先我还是把整个代码贴出来:

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
// Vector.h
/*
 * vector class
 * Author: Tanky Woo
 * Blog:   www.WuTianQi.com
 * Data:   2010.11.12
 */
 
 
#ifndef VECTOR_H
#define VECTOR_H
 
template <typename Object>
class Vector
{
public:
	explicit Vector(): objects(0), theSize(0),theCapacity(0) {}
 
	explicit Vector(int initSize)
		: theSize(initSize), theCapacity(initSize + SPARE_CAPACITY)
	{
		objects = new Object[theCapacity]; 
		for(int i=0; i<initSize; ++i)
			objects[i] = 0;
	}
 
	Vector(const Vector & rhs)   
	{ operator=(rhs); }
 
	~Vector()
	{ delete [] objects; }
 
	const Vector & operator= (const Vector & rhs)
	{	
		if(this != &rhs)      // check for aliasing
		{
			delete [] objects;
			theSize= rhs.size();
			theCapacity = rhs.capacity();
 
			objects = new Object[ capacity() ];
			for(int k = 0; k < size(); ++k)
				objects[k] = rhs.objects[k];
		}
		return *this;
	}
 
	void resize(int newSize)
	{
		if(newSize > theCapacity)
			reserve(newSize * 2 + 1);
		theSize = newSize;
	}
 
	void reserve(int newCapacity)
	{
		if(newCapacity < theSize)
			return;
 
		Object * oldArray = objects;
 
		objects = new Object[ newCapacity ];
		for(int k = 0; k < theSize; ++k)
			objects[k] = oldArray[k];
 
		theCapacity = newCapacity;
 
		delete [] oldArray;
	}
 
	Object & operator[] (int index)
	{
		return objects[index];
	}
	const Object & operator[] (int index) const
	{
		return objects[index];
	}
 
	bool empty() const
	{
		return size() == 0;
	}
	int size() const
	{
		return theSize;
	}
	int capacity() const
	{
		return theCapacity;
	}
 
	void push_back(const Object & x)
	{
		if(theSize == theCapacity)
			reserve(2 * theCapacity + 1);
		objects[ theSize++ ] = x;
	}
	void pop_back()
	{
		theSize--;
	}
 
	const Object & back() const
	{
		return objects[theSize-1];
	}
 
	typedef Object * iterator;
	typedef const Object * const_iterator;
 
	iterator begin()
	{ 	return &objects[0]; }
	const_iterator begin() const
	{ 	return &objects[0]; }
	iterator end()
	{ 	return &objects[size()]; }
	const_iterator end() const
	{ 	return &objects[size()]; }
 
	enum{ SPARE_CAPACITY = 16 };
private:
	int theSize;
	int theCapacity;
	Object * objects;
};
 
#endif

接下来这个是我写的一个测试用的小程序:

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
// Main.cpp
#include "Vector.h"
#include <iostream>
using namespace std;
 
int main()
{
	Vector<int> first;
	Vector<int> second(4);
	cout <<"Pre:\n" << first.size() << endl << first.capacity() << endl;
	first = second;
	cout <<"Post:\n" << first.size() << endl << first.capacity() << endl;
	cout << endl;
 
	int preindex = first.size();
	for(int i=1; i<=10; ++i)
		first.push_back(i);
	cout << "The third element is: " << first[preindex-1+3] << endl;
	cout << endl;
 
	cout << "The last element:" << endl;
	cout << "Before pop: " << first.back() << endl;
	first.pop_back();
	cout << "After pop: " << first.back() << endl;
	return 0;
}

先开始我不是这么写的。说真的,今天写这个我感触很深,现在一直忙于看书,掌握新知识,却没有发现,自己的动手能力越来越差了,以前学C时,经常找一个程序自己敲在电脑上实现,现在却只是对程序扫一遍,结果导致自己会的与不会的都不知道。今天把这个程序打了一遍,结果BUG太多了。

1.模板类的借口与实现分离问题:
我先开始是把类模板的借口和实现分离了。
把实现文件写成了:

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
#include "Vector.h"
#include <iostream>
using namespace std;
 
 
template <typename Object>
Vector<Object>::Vector() 
{
 
	objects = new Object[10];
	theSize = 10;
	the Capacity = 10;
 
}
 
template <typename Object>
Vector<Object>::Vector(int initSize = 0) 
		: theSize(initSize), theCapacity(initSize + SPARE_CAPACITY)
{ 
	objects = new Object[theCapacity]; 
}
 
template <typename Object>
Vector<Object>::Vector(const Vector<Object> & rhs) : objects(NULL)
{
	operator=(rhs); 
}
 
template <typename Object>
Vector<Object>::~Vector()
{
	delete [] objects;
}
 
 
template <typename Object>
const Vector<Object> & Vector<Object>::operator= (const Vector<Object> & rhs)
{
	if(this != &rhs)      // check for aliasing
	{
		delete [] objects;
		theSize= rhs.size();
		theCapacity = rhs.capacity();
 
		objects = new Object[ capacity() ];
		for(int k = 0; k < size(); ++k)
			objects[k] = rhs.objects[k];
	}
	return *this;
}
 
template <typename Object>
void Vector<Object>::resize(int newSize)
{
	if(newSize > theCapacity)
		reserve(newSize * 2 + 1);
	theSize = newSize;
}
 
template <typename Object>
void Vector<Object>::reserve(int newCapacity)
{
	if(newCapacity < theSize)
		return;
 
	Object * oldArray = objects;
 
	objects = new Object[ newCapacity ];
	for(int k = 0; k < theSize; ++k)
		objects[k] = oldArray[k];
 
	theCapacity = newCapacity;
 
	delele [] oldArray;
}
 
template <typename Object>
Object & Vector<Object>::operator[] (int index)
{
	return objects[index];
}
 
template <typename Object>
const Object & Vector<Object>::operator[] (int index) const
{
	return objects[index];
}
 
template <typename Object>
bool Vector<Object>::empty() const
{
	return size() == 0;
}
 
template <typename Object>
int Vector<Object>::size() const
{
	return theSize;
}
 
template <typename Object>
int Vector<Object>::capacity() const
{
	return theCapacity;
}
 
template <typename Object>
void Vector<Object>::push_back(const Object & x)
{
	if(theSize == theCapacity)
		reserve(2 * theCapacity + 1);
	objects[ theSize++ ] = x;
}
 
template <typename Object>
void Vector<Object>::pop_back()
{
	theSize--;
}
 
template <typename Object>
const Object & Vector<Object>::back() const
{
	return objects[theSize-1];
}

最后出现这个问题:

1>main.obj : error LNK2019: 无法解析的外部符号 “public: class Vector const & __thiscall Vector::operator=(class Vector const &)” (??4?$Vector@H@@QAEABV0@ABV0@@Z),该符号在函数 _main 中被引用
1>main.obj : error LNK2019: 无法解析的外部符号 “public: int __thiscall Vector::size(void)const ” (?size@?$Vector@H@@QBEHXZ),该符号在函数 _main 中被引用
1>main.obj : error LNK2019: 无法解析的外部符号 “public: int __thiscall Vector::capacity(void)const ” (?capacity@?$Vector@H@@QBEHXZ),该符号在函数 _main 中被引用
…….

最终找到了一篇帖子,里面提到了类模板的接口与实现分离问题,上面这么说的:
因为模板类在编译的时候就相当于宏定义,分两个文件是找不到的。
解决办法:
1.类模板定义和实现在同一文件。
2.在main文件中连续包含定义文件和实现文件.
3.在类模板头文件的最后面,#endif前面加上”#include “Vector.cpp””
4.export的分别编译问题。
后两者据说和编译器有关,反正第3个我在VS2008下测试不成功。第四个现实暂时未支持export关键字。
后来我在CSDN上找到了一个讨论这方面问题的帖子:
http://topic.csdn.net/t/20061221/22/5247963.html
这里面讨论后的基本思想就是:
1.模板类的借口与实现最好不要分离。
2.把主函数放入#include xxx.cpp文件是一个不好的编程风格。
这个文章也讨论了LNK2019问题:
http://qubo.im/2009/10/30/lnk2019%E5%8E%9F%E5%9B%A0%E4%B9%8B%E4%B8%80%EF%BC%9Ac%E4%B8%8D%E6%94%AF%E6%8C%81%E7%B1%BB%E6%A8%A1%E6%9D%BF%E7%9A%84%E5%A3%B0%E6%98%8E%E4%B8%8E%E5%AE%9E%E7%8E%B0%E7%9A%84%E5%88%86%E7%A6%BB/

2.对private,public的认识问题。
一直以来,我对private,public等处于一个错误的认识中,我认为,private成员是某个类对象的,所以这个类对象的私有成员对外都是私有的。直到今天,我才认识到,private是相对与类类型的,也就是说,private对于定义他的类型T是私有的,只能这个类类型的对象可以访问。
总结起来也就一句话:private是针对类类型,而不是某个类对象的。

今天收获真的很大,不光把vector一些基本内容实现了,还学习了好多其他知识,赞一个。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《vector的实现以及模板类的接口与实现分离问题》有83个想法

  1. 引用:“数据结构入门还是严蔚敏老师的好”
    我挺讨厌她那本书的!基本上都是伪代码,而且一点都没有代码规范,不愧是搞数学出身的~
    我看的是“Data Structures and Algorithm Analysis in C”(作者:Mark Allen Weiss)的中文译本

    1. @C瓜哥,
      你也是看的Weiss的啊,哈哈。
      不过那本涉及到了一些算法,而一些基本的数据结构没讲到,反正我看的C++版是这样的。

      其实真正算法都应该是伪代码或pascal实现的。搞NOI的也都是用的pascal。

      我最近就准备买本pascal书看看。

      1. @Tanky Woo,
        严蔚敏总喜欢把一个简单的东西说得很复杂,还有就是她的伪代码中经常有些什么
        a,b,c,d,e,f,g,i,j,k什么的,很让人无语啊
        ……
        Weiss不高端,他的东西反而容易懂得多。
        ……
        数据结构和算法是一家嘛,不是什么大问题
        ……
        pascal 让人很抓狂,什么:= 什么begin、end的,麻烦死了(相比C语言的花括号……)

        1. @C瓜哥, 汗。。。那学汇编你不是更受不了了?
          严蔚敏还行吧,算法导论也是用伪代码写的。应聘写的那就是具体实现了。

          其实数据结构不必要在语言细节上做过多解释的,所以才选择伪代码。

      2. @Tanky Woo,
        1、老实说,汇编我还没怎么学呢~汗
        2、这不只是学理论、学思想的,很多时候要会写的
        3、在软件项目中,数据结构经常用的。链表、堆栈、树等等,不过只是用而已,
        不用自己再去实现一个结构。举个例子,用户登录进服务器,应该把他的信息写进一个链表里面吧,
        登出应该把他移出吧~ 再比如树,比如资源管理器的文件的树形视图,怎么遍历树这些代码是会
        经常用到的。再如,怎样把树的信息完整地保存进数据库,怎么样读出来,这些都是必须要会写
        代码的。

        不过更多时候,是要自己实现数据结构的

        1. @C瓜哥,
          额。瓜哥太给力了,写了那么多。。。。
          这年头,我觉得汇编只需要了解就OK了,其实以后完全有机会练习汇编->debug
          数据结构其实很基础的,音乐用的太多了。就像瓜哥举的例子,还有比如hash压缩数据,编码等,都需要数据结构。

          其实自己尝试实现数据结构,比如STL里的vector,string,都很锻炼人。

          再次感谢瓜哥,在瓜哥帮助下,读者墙回来了。。。

        2. @C瓜哥,
          其实我说的是数据结构最基本的应用,不管是高级开发人员还是刚从培训学校出来的人员,都会用到的。
          (以上这条,我现在才体会出来,汗死了)

          自己试着写数据结构,一是为了更好的理解它,二是为了更好的使用它,才有可能更好的改造它,或者实现新的数据结构

  2. private是针对类类型,而不是某个类对象的

    我也很久才发现这个。。汗一个,往往在类之内还傻乎乎地调用GetXXX()

    但当这个GetXXX()是虚函数时还是需要的

发表评论

电子邮件地址不会被公开。 必填项已用*标注