今天最大的收获就是把实现这个vector模板类,虽然花费了5个小时左右,但是期间学到的知识实在是太值得了! 这个模板类是来至《数据结构与算法分析–C++描述》 ,Weiss写的,很好的一本书,不过这本书不是针对数据结构初学者的,也不是针对C++初学者的,数据结构入门还是严蔚敏老师的好。 首先我还是把整个代码贴出来:
// Vector.h
/*
* vector class
* Author: Tanky Woo
* Blog: www.WuTianQi.com
* Data: 2010.11.12
*/
#ifndef VECTOR_H
#define VECTOR_H
template
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 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
接下来这个是我写的一个测试用的小程序:
// Main.cpp
#include "Vector.h"
#include
using namespace std;
int main()
{
Vector first;
Vector 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.模板类的借口与实现分离问题: 我先开始是把类模板的借口和实现分离了。 把实现文件写成了:
#include "Vector.h"
#include
using namespace std;
template
Vector::Vector()
{
objects = new Object[10];
theSize = 10;
the Capacity = 10;
}
template
Vector::Vector(int initSize = 0)
: theSize(initSize), theCapacity(initSize + SPARE_CAPACITY)
{
objects = new Object[theCapacity];
}
template
Vector::Vector(const Vector & rhs) : objects(NULL)
{
operator=(rhs);
}
template
Vector::~Vector()
{
delete [] objects;
}
template
const Vector & 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;
}
template
void Vector::resize(int newSize)
{
if(newSize > theCapacity)
reserve(newSize * 2 + 1);
theSize = newSize;
}
template
void Vector::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
Object & Vector::operator[] (int index)
{
return objects[index];
}
template
const Object & Vector::operator[] (int index) const
{
return objects[index];
}
template
bool Vector::empty() const
{
return size() == 0;
}
template
int Vector::size() const
{
return theSize;
}
template
int Vector::capacity() const
{
return theCapacity;
}
template
void Vector::push_back(const Object & x)
{
if(theSize == theCapacity)
reserve(2 * theCapacity + 1);
objects[ theSize++ ] = x;
}
template
void Vector::pop_back()
{
theSize--;
}
template
const Object & Vector::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一些基本内容实现了,还学习了好多其他知识,赞一个。