首页 > 代码库 > Vector模板类的建立与实现(一)

Vector模板类的建立与实现(一)

最近学习了数据结构,对线性表有了比较深刻的认识,并和c++中容器的实现对照了下,有了点小收获,记录下来。。

1,首先线性表有2种存储结构:顺序存储结构,链式存储结构。(先讲顺序存储,之后看链表list的时候再说)顺序存储就相当于数组,连续的存储地址,插入和删除要移动大量的数据元素,因为地址是连续的,但是随机访问能力好,也就是下标访问元素的能力。

2.对c++中vector类模板的实现,改变了数组固定大小的缺点,可以动态添加或删除元素改变容器的大小,有很多的函数成员,使用起来也很方便。

其实vector就是可变大小的数组,支持快速随机访问,除了尾部之外的地方插入和删除元素很慢。

3.自己写了一个vector类模板,只是实现了部分功能,一般的大小,插入,删除,访问等。。而且程序也有好多问题,之后等看了源码再改吧。。。

4.代码如下Vector.h为头文件,成员函数直接在里面实现了。。。

/*vector是可变大小的数组,是顺序存储结构,支持快速的随机访问,在尾部之外的位置插入和删除元素很慢*/
/*类模板*/
#include<cassert>
template<typename T>
class Vector
{
private:
    T *elem;
    int thesize;
    int thecapacity;
public:
    enum{ SPARE_CAPACITY = 16 };
    typedef T* iterator;
    typedef const T* const_iterator;
    /******************************************构造函数******************************************/
    //构造函数,,   问题,它的元素是怎么进行值初始化的???
    explicit Vector(int initsize = 0) :thesize(initsize), thecapacity(initsize + SPARE_CAPACITY)
    {
        elem = new T[thecapacity];
        assert(elem != NULL);    //存储分配失败则退出;
    }
    explicit  Vector(int initsize, T value) :thesize(initsize), thecapacity(initsize + SPARE_CAPACITY)
    {
        elem = new T[thecapacity];
        assert(elem != NULL);    //存储分配失败则退出;
        for (int i = 0; i != thesize; ++i)
            elem[i] = value;
    }
    //接受两个迭代器创建拷贝的构造函数 ,这里的迭代器的创建是指针,见上面
    Vector(iterator b, iterator e)
    {
        thesize = e - b;
        thecapacity = thesize + SPARE_CAPACITY;
        elem = new T[thecapacity];
        assert(elem != NULL);
        for (int i = 0; b != e&&i != thesize; ++i)
        {
            elem[i] = *b;
            ++b;
        }
    }

    //拷贝构造函数,接受一个容器为另一个容器的拷贝
    Vector(const Vector &rhs)
    {
        thesize = rhs.thesize;
        thecapacity = rhs.thecapacity;
        elem = new T[thecapacity];
        assert(elem != NULL);
        for (int i = 0; i != thesize; ++i)
            elem[i] = rhs.elem[i];
    }
    /***************************析构函数****************************/
    ~Vector()
    {
        delete[] elem;
    }
    /***************************************************************************/
    //赋值运算符
    Vector &operator=(const Vector & rhs)
    {
        if (this != &rhs) //防止自赋值
        {
            delete[]elem;
            thesize = rhs.thesize;
            thecapacity = rhs.thecapacity;
            elem = new T[thecapacity];
            assert(elem != NULL);
            for (int i = 0; i != thesize; ++i)
                elem[i] = rhs.elem[i];
        }
        return *this;
    }
//待实现
//swap函数的实现,通常比从一个向另一个容器拷贝元素快,只是交换了两个容器内部的数据结构,元素本身没有交换。。 //交换的是相同类型的容器。 //assign,赋值函数的实现 /**************************************************************************************/ bool empty()const //常量成员函数,不改变类的成员 { return thesize == 0; } int size() const //要修改,,返回类型为vector<T>::size_type { return thesize; } iterator begin() { return &elem[0]; } iterator end() { return &elem[thesize]; } const_iterator begin() const { return &elem[0]; } const_iterator end() const { return &elem[thesize]; } /********************************************关系运算符**********************************/ //关系运算符的实现==,!=,> ,>=, <, <= bool operator==(const Vector<T>& rhs) { if (this->thesize == rhs.thesize) { int cnt = 0; for (int i = 0; i != thesize; i++) if (this->elem[i] == rhs.elem[i]) ++cnt; if (cnt == thesize) return true; } return false; } //是否要友元函数???,判断两个vector是否相等 bool operator!=(const Vector<T>& rhs) { return !(*this== rhs); } /*****************************************管理容器大小***********************************************/ int capacity() const { return thecapacity; } void reserve(int newcapacity) //分配至少容纳newcapacity个的元素空间,,,进行内存分配,释放 { if (newcapacity < thecapacity) return; T *oldarray = elem; elem = new T[newcapacity]; for (int i = 0; i != thesize; ++i) elem[i] = oldarray[i]; thecapacity = newcapacity; delete[] oldarray; } void shrink_to_fit() //将capacity()减少为与size()相同大小 { reserve(thesize); } /*******************************************改变容器的大小**********************************************/ void resize(int newsize) //调整它的大小,若newsize<thesize,多的元素被丢弃,若相反,添加新元素,进行值初始化 { if (newsize>thecapacity) reserve(newsize * 2 + 1); thesize = newsize; } void resize(int newsize, T thevalue) //新添进来的元素初始化为thevalue { if (newsize > thecapacity) { reserve(newsize * 2 + 1); } for (int i = thesize; i < newsize; ++i) elem[i] = thevalue; thesize = newsize; } /**************************************访问操作***************************************/ T &operator[](int index) //要修改,下标index类型是vector<T>::size_type; { if (index<0 || index >= thesize) return; return elem[index]; } const T &operator[](int index) const { if (index<0 || index >= thesize) return; return elem[index]; } T &front() { if (!this->empty()) return elem[0]; } T &back() { if (!this->empty()) return elem[thesize - 1]; } /******************************************插入操作*************************************/ //向容器插入元素,vector不支持push_front,但insert可以实现插入vector的任何位置,但是注意在vector除尾部之外的任何位置很慢,很耗时。。 void push_back(const T &x) { if (thesize == thecapacity) reserve(2 * thecapacity); elem[thesize++] = x; } //这里的迭代器是指指针,插入了一个元素。 iterator insert(iterator b, T value) { if (b < this->begin() || b> this->end()) //b可以为尾后迭代器,这里不知道怎么处理异常就返回尾后迭代器吧 return this->end(); if (thesize == thecapacity) reserve(thesize * 2); for (iterator p = this->end(); p > b; p--) *p = *(p - 1); *b = value; thesize++; return b; } /********************************************删除操作***************************************/ void pop_back() { thesize--; } //删除了一个元素 iterator erasea(iterator b) { if (b < this->begin() || b >= this->end()) //确保迭代器在范围内,,否则未定义,b不能为尾后迭代器 return this->end(); iterator q = b + 1; iterator p = this->end() - 1; for (; b < p; b++) *b = *(b + 1); thesize--; if (thesize <= thecapacity / 4) //防止删除后空闲空间太大,浪费空间 { reserve(thecapacity / 2); } return q; } /*void clear() //有问题 { delete[] elem; }*/ };

测试代码:

#include <string>
#include<iostream>
#include<cassert>
#include"Vector.h"     //注意当这里不是标准库的头文件,是自己写的,要用双引号,整了好久,还以为程序出错了。。
using namespace std;
int main()
{
    // 利用构造函数
    Vector<int> v1; 
    Vector<int> v2(5, 9);
    Vector<int> v3(v2);
    Vector<int> v4(v2.begin(), v2.end());
    if (v1.empty())
    cout <<"v1为空,大小为:"<< v1.size() << endl;
    cout << "向v1插入元素:";
    int a;
    while (cin >> a)
        v1.push_back(a);
    if (!v1.empty())
        cout << "v1不为空,大小为:" << v1.size() << "容量为:" << v1.capacity() << endl;
    cout << "元素为:";
    for (Vector<int>::iterator iter = v1.begin(); iter != v1.end(); ++iter)
        cout << *iter << "   ";
    cout << endl;
    cout << "重新插入后:";
    v1.insert(v1.begin() + 1, 4);
    cout << "此时v1大小为:" << v1.size() << "容量为:" << v1.capacity() << endl;
    cout << "元素为:";
    for (Vector<int>::iterator iter = v1.begin(); iter != v1.end(); ++iter)
        cout << *iter << "   ";
    cout << endl;
    cout << "删除元素后为:";
    v1.pop_back();
    for (Vector<int>::iterator iter = v1.begin(); iter != v1.end(); ++iter)
        cout << *iter << "   ";
    cout << endl;
    cout << "再次删除元素后为:";
    v1.erasea(v1.begin() + 2);
    for (Vector<int>::iterator iter = v1.begin(); iter != v1.end(); ++iter)
        cout << *iter << "   ";
    cout << endl;
    cout << "v2元素为:";
    for (Vector<int>::iterator iter = v2.begin(); iter != v2.end(); ++iter)
            cout << *iter << "   ";
        cout << endl;
    cout << "v3元素为:";
    for (Vector<int>::iterator iter = v3.begin(); iter != v3.end(); ++iter)
            cout << *iter << "   ";
        cout << endl;
    cout << "v4元素为:";
    for (Vector<int>::iterator iter = v4.begin(); iter != v4.end(); ++iter)
            cout << *iter << "   ";
        cout << endl;
    if (v1 == v3)
            cout << "v1与v3相等";

    return 0;
}

 

Vector模板类的建立与实现(一)