梁越

实现vector插入扩容

0 人看过

联发科提前批难点记录

#ifndef _MY_VECTOR_HPP_
#define _MY_VECTOR_HPP_

template<typename T>
class MyVector
{

public:
    // 构造函数
    MyVector()
    {
        //这里默认数组大小为10
        //但是vector文件中默认构造的方式是0, 之后插入按照1 2  4  8  16 二倍扩容。注(GCC是二倍扩容,VS13是1.5倍扩容
        data = new T[10];
        _capacity = 10;
        _size = 0;
    }
    ~MyVector()
    {
        delete[] data;
    }
    //reserve只是保证vector的空间大小(_capacity)最少达到它的参数所指定的大小n。在区间[0, n)范围内,预留了内存但是并未初始化
    void reserve(size_t n)
    {
        if(n>_capacity)
        {
            data = new T[n]; 
            _capacity = n;
        }
    }
    //向数组中插入元素
    void push_back(T e)
    {
        //如果 当前容量已经不够了, 重新分配内存, 均摊复杂度O(1)
        if (_size == _capacity)
        {
            resize(2 * _capacity);
        }
        data[_size++] = e;
    }
    //删除数组尾部的数据,同时动态调整数组大小,节约内存空间
    T pop_back()
    {
        T temp = data[_size];
        _size--;
        //如果 容量有多余的,释放掉
        if (_size == _capacity / 4)
        {
            resize(_capacity / 2);
        }
        return temp;
    }
    //获取当前数组中元素的个数
    size_t size()
    {
        return _size;
    }
    //判断数组是否为空
    bool empty()
    {
        return _size==0?1:0;
    }
    //重载[]操作
    int &operator[](int i)
    {
        return data[i];
    }
    //获取数组的容量大小
    size_t capacity()
    {
        return _capacity;
    }
    //清空数组,只会清空数组内的元素,不会改变数组的容量大小
    void clear()
    {
        _size=0;
    }
private:
    T *data;    //实际存储数据的数组
    size_t _capacity; //容量
    size_t _size;  //实际元素个数
    //扩容
    void resize(int st)
    {
        //重新分配空间,在栈区新开辟内存,然后将以前数组的值赋给他,删除以前的数组
        T *newData = new T[st];
        for (int i = 0; i < _size; i++)
        {
            newData[i] = data[i];
        }
        //实际使用时是清除数据,但不会释放内存
        delete[] data;
        data = newData;
        _capacity = st;
    }

};

#endif //_MY_VECTOR_HPP_