数据结构:向量Vector的实现与代码分析

2017-01-08 08:19:30来源:CSDN作者:u012175089人点击

Vector是比较常用的结构,在C++的STL中就有了vector的实现,在头文件<vector>中可以看到。

但是STL的实现就像一个超级大的蛋糕,我们不可能一口一口地吃下去。最好的办法是从基础的思想开始,自己跟着写一个简单版本的Vector。

vector究竟是什么?

其实本质上就是数组,只是经过封装后,可以忽略数组的长度限制。除了这一点,其他的特性跟数组都差不多。

对于队首和队中插入和删除都要耗费O(N)的时间,都是支持随机访问,其实这个就是本来的数组原来的操作,只是封了一层而已。

另外后面的算法研究,也会用到。

让我们把STL的各种数据结构,一点一点地吃掉。

下面看一下vector的C++实现和详细分析。这个是比C++ STL简单的版本,但是思想是一样的。

////  Vector.h//  HelloWorld////  Created by feiyin001 on 17/1/7.//  Copyright (c) 2017年 FableGame. All rights reserved.//#ifndef __HelloWorld__Vector__#define __HelloWorld__Vector__template <typename Object>class Vector{public:    //默认构造函数,explicit是显式的意思,防止隐式转换,例如 Vector<int> a = 123;这类语句被编译成功    //theSize 这个是对外的size,表示已经有多少个object在vector里面了。    //theCapacity 这个是vector内数组实际的大小,SPARE_CAPACITY是预留的空间,防止每次插入的时候都要去重新申请一个数组。    explicit Vector(int initSize = 0): theSize(initSize), theCapacity(initSize + SPARE_CAPACITY)    {        objects = new Object[theCapacity];//申请一个容量为theCapacity的动态数组,vector只是保留了数组的指针而已。    }        //复制构造函数,方便用现有的Vector对象,来创建一个新的对象。这里直接调用了复制赋值运算符。    Vector(const Vector & rhs):objects(nullptr)    {        operator = (rhs);    }        //析构函数,构造函数里面的new和new[]一定要与析构函数里面的delete和delete[]对应,否则就是内存泄漏了。    ~Vector()    {        delete [] objects;    }        //复制赋值运算符,将一个vector复制给另外一个。    const Vector& operator=( const Vector& rhs )    {        if (this != & rhs)//如果地址相同,就不应该进行赋值了,直接返回        {            delete [] objects;//数组是不能直接复制的,它们有固定的大小,所以只能删除掉,然后新建一个一样大小的            theSize = rhs.theSize;            theCapacity = rhs.theCapacity;            objects = new Object[rhs.theCapacity];            //一个一个对象进行复制,如果Object内带有指针成员,这里一般要求Object是重载复制赋值运算符的,否则可能是浅复制了            for (int k = 0; k < rhs.theSize; k++)            {                objects[k] = rhs.objects[k];            }        }        return *this; //返回自身,是为了实现连续赋值的效果,例如vector<int> a,b,c; a = b = c;    }        //重置vector内对象的数量    void resize(int newSize)    {        if (newSize > theCapacity)        {            reserve(newSize * 2 + 1);//新的大小是比原来的容量都打,才需要扩展容量,每次翻倍,之所以+1,是防止为0的情况。        }        theSize = newSize;//新的对象数量,如果比原来的多,则会多出一部分可能为初始化的值,如果比原来的小,则减少的部分对象就当做无效的数据了。    }        //修改vector的容量大小,    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;//删除旧的数组    }        //重载了[]运算符,使得vector能够像基础的数组一样通过下标访问,带const的版本是在vector对象是const的时候使用的。    Object & operator[](int index)    {        return objects[index];    }    const Object& operator[](int index) const    {        return objects[index];    }        //vector为空    bool empty() const    {        return theSize == 0;    }        //返回对象的个数    int size() const    {        return theSize;    }        //vector内数组实际的大小    int capacity() const    {        return theCapacity;    }        //把对象放到数组尾,消耗的是O(1)的时间    void push_back(const Object& x)    {        if (theSize == theCapacity)        {            reserve(2* theCapacity + 1);//如果已经所有位置都被使用了,就要扩容了        }        objects[theSize++] = x;//先赋值,再对theSize自增,记得C++的下标是从0开始id。    }        //弹出最后一个对象,直接把队尾往前移动就行了    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;//实际对象的数量,同时这标志着这个下标是队尾下一个的对象的下标,队尾的下标是theSize-1.    int theCapacity;//数组实际的大小,每次theSize要超过的时候,才重新申请一个。    Object* objects;//对象数组};#endif /* defined(__HelloWorld__Vector__) */
为了区分STL里面的vector,加了个域名Fable。没错,我就是肥宝。

下面看一下简单的测试代码。

////  main.cpp//  HelloWorld////  Created by feiyin001 on 17/01/04.//  Copyright (c) 2016年 Fable. All rights reserved.//#include "Vector.h" #include <iostream>using namespace Fable;int main(int argc, char* argv[]){    //声明一个Vector<int>对象    Vector<int> myVec;//编译到这里的时候,编译器就会生成了参数为int的Vector实例。        //循环赋值    for (int i = 0; i < 100; i++) {        myVec.push_back(i);    }        //遍历,这里的迭代器,实际上只是Object*,当然STL里面的更加复杂,有更加丰富的实现。    for (Vector<int>::iterator iter = myVec.begin(); iter != myVec.end(); ++iter) {        std::cout << *iter << std::endl;    }    return 0;}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台