欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

迭代器实现Vector

程序员文章站 2022-04-16 08:14:42
...

vector模型是一个动态数组,它本身是“将元素至于动态数组中加以管理”的一个抽象概念,但是c++标准并未要求以动态数组实作vector。
在使用标准库里面的vector时,必须包含头文件#include<vector> 其中型别vector是一个定义于namespace std的template。

namespace std{
  template<class T,class Allocator =allocator<T>>
  class vector;
}

迭代器实现Vector

通过查看标准库里面的vector函数,利用迭代器Iterator,模拟实现vector,代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
template<typename T>
class Vector
{
public:
    typedef T* Iterator;
    Vector()
        :_start(0)
        , _finish(0)
        , _endOfstorage(0)
    {}
    Vector(const T* str, size_t size)//构造size个元素
        :_start(new T[size])
        , _finish(_start)//(没放空间时)//_finish(_start+size)(放了空间)
        , _endOfstorage(_start + size)
    {
        //memcpy(_start,str,sizeof(T)*size);
        for (size_t i = 0; i<size; ++i)
        {
            *_finish++ = str[i];//_start[i]=str[i];
        }
    }
    Vector(const Vector<T>& v)//拷贝构造函数
    {
        size_t size = Size();
        _start = new T[size];
        for (size_t i = 0; i<size; i++)
        {
            _start[i] = v._start[i];
        }
        _finish = _start + size;
        _endOfstroage = _finish;
    }
    Vector& operator=(const Vector<T>& v)//赋值运算符重载
    {
        size_t size = v.Size();
        if (this != &v)
        {
            T*tmp = new T[size];
            for (size_t i = 0; i<size; i++)//深拷贝
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
            _start = tmp;
            _finish = _start + size;
            _endOfstorge = _finish;
        }
        return *this;
    }
    ~Vector()
    {
        if (_start)
        {
            delete[] _start;
            _start = NULL;
        }
    }
    //////////////////////Iterator////////////////////////////  
    Iterator Begin()    //迭代器  
    {
        return _start; //Begin和_start类型一致 
    }
    Iterator End()
    {
        return _finish;
    }
    ///////////////////Modify//////////////////////////////// 
    void PushBack(const T& data)
    {
        CheckCapacity();
        *_finish = data;
        ++_finish;
    }
    void PopBack()
    {
        --_finish;
    }
    void Insert(size_t pos, const T& data)
    {
        size_t size = Size();
        CheckCapacity();
        assert(pos<size);
        for (size_t i = size; i>pos; --i)
        {
            _start[i] = _start[i - 1];
        }
        _start[pos] = data;
        ++_finish;
    }
    void Erase(size_t pos)
    {
        size_t size = Size();
        assert(pos<size)
        for (size_t i = pos; i<size; i++)
        {
            _start[i] = start[i + 1];
        }
        --_finish;
    }

    //////////////////capacity//////////////////////////// 
    size_t Size()const
    {
        return _finish - _start;
    }
    size_t CapaCity()const
    {
        return _endOfstorage - _start;
    }
    bool Empty()const//判空
    {
        if (_atart == _finish)
        {
            return true;
        }
        return false;
    }
    void Resize(size_t newSize, const T& data = T())//改变大小
    {
        size_t size = Size();//原来元素大小
        size_t capacity = CapaCity();//原来容量
        //1.newSize比size小
        if (newSize<size)
        {
            _finish == _start + newSize;
        }
        //2.newSize比size大,但比capacity小
        else if (newSize>size&&newSize<capacity)
        {
            for (size_t i = size; i<newSize; i++)
            {
                //*finish++=data;
                _start[i] = data;
            }
            _finish = _start + newSize;
        }
        //newSize比capacity大
        else
        {
            T* tmp = new T[newSize];//开辟新空间
            for (size_t i = 0; i<size; i++)//搬移原空间的元素
            {
                tmp[i] = _start[i];
            }
            for (size_t i = size; i<newSize; i++)//把新增加的元素加进来
            {
                tmp[i] = data;
            }
            delete[] _start;//释放旧空间
            _start = tmp;
            _finish = _start + newSize;
            _endOfstorage = _finish;
        }
    }

    //////////////Element Acess(元素访问)/////////////////////////// 
    T& operator[](size_t index)//随机访问(下标)
    {
        size_t capacity = CapaCity();
        assert(index <= capacity);
        return _start[index];
    }
    const T& operator[](size_t index)const
    {
        size_t capacity = CapaCity();
        assert(index <= capacity);
        return _start[index];
    }
    T& Front()
    {
        return *_start;
    }
    const T& Front()const
    {
        return *_start;
    }
    T& Back()
    {
        return *(_finish - 1);
    }
    const T& Back()const
    {
        return *(_finish - 1);
    }
    void Clear()
    {
        _finish = _start;
    }

    friend ostream& operator<<(ostream& os, const Vector<T>& v)
    {
        for (size_t i = 0; i<v.Size(); i++)
        {
            os << v[i] << " ";
        }
        os << endl;
        return os;
    }
    /*friend ostream& operator<<(ostream& os,  Vector<T>* v)//通过迭代器重载
    {
        Vector<int>::Iterator it = v.Begin();
            while(it!=v.End())
            {
                cout<<*it<<" ";
                ++it;
            }
            os << endl;
            return os;
    }*/
private:
    void CheckCapacity()
    {
        size_t size = Size();
        size_t capacity = CapaCity();
        size_t newcapacity = 2 * capacity + 2;
        if (size >= capacity)
        {
            //增容
            T* tmp = new T[newcapacity];
            //拷贝元素
            //if(_start)
            //memcpy(tmp,_start,size*sizeof(T));//浅拷贝(导致两个字符串公用同一块空间)但是效率高
            //出了函数作用域,要销毁v,销毁旧空间时出现问题
            for (size_t i = 0; i<size; i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;//释放旧空间
            _start = tmp;
            _finish = _start + size;
            _endOfstorage = _start + newcapacity;
        }
    }

private:
    T* _start;
    T* _finish;
    T* _endOfstorage;
};
void TestVector()//测试函数
{
    int arr[]={1,2,3,4};
    Vector<int>v(arr,sizeof(arr)/sizeof(arr[0]));
    cout<<"Size="<<v.Size()<<endl;
    cout<<"Capacity="<<v.CapaCity()<<endl;
    cout<<v<<endl;
    Vector<int>::Iterator it=v.Begin();
    while(it!=v.End())
    {
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
    v.PushBack(5);
    cout << v << endl;
    v.Insert(0, 0);
    cout << v << endl;

    v.Resize(20);
    cout << "Size=" << v.Size() << endl;
    cout << "Capacity=" << v.CapaCity() << endl;

    v.Clear();
    cout << "Size=" << v.Size() << endl;
    cout << "Capacity=" << v.CapaCity() << endl;
}

int main()
{
    TestVector();
    system("pause");
    return 0;
}
相关标签: iterator class