Blog·Tanky WooABOUTRSS

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

12 Nov 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

今天最大的收获就是把实现这个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一些基本内容实现了,还学习了好多其他知识,赞一个。