C++入门之vector的底层实现详解

template <class T>
class vector
{
public:
    ~vector()
    {
        delete _start;
        _start = _finish = _end_of_storage = nullptr;
    }
private:
    T* _start;         //顺序表的头
    T* _finish;        //顺序表有效长度位置
    T* _end_of_storage; //顺序表末尾
};

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr) {}

size_t size() const    //加const是保证const对象也可以用
{
    return _finish - _start;
}

size_t capacity() //加const是保证const对象也可以用
{
    return _end_of_storage - _start;
}

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];               //先开辟一块空间
        size_t sz = size();              //保留原来的有效数据大小,且一定要先保存
        if (_start)        //一定要判断这个,因为最开始_start为空,那么就只需要开空间
        {
            memcpy(tmp, _start, sizeof(T) * n);  //把原来的数据拷贝进新空间
            delete _start;  //释放原来的空间
        }
        _start = tmp;                    //移交空间
        _finish = _start + sz;           //更新_finish
        _end_of_storage = _start + n;    //更新_end_of_storage
    }
}

void resize(size_t n,const T& val = T())
{
    if(n>capacity()) reserve(n);
    for(size_t i = size();i<n;i++)
    {
        _start[i] = val;
    }
    _finish = _start + n;    
}

typedef T* iterator;              //普通迭代器
typedef const T* const_iterator;  //const迭代器
//因此返回首尾迭代器的接口,博主便一并写下来
iterator begin() {return _start;}
iterator end() {return _finish;}        //普通接口
const_iterator begin() const {return _start;}
const_iterator end() const {return _finish;}  //const接口

void push_back(const T& val)
{
    if(size() == capacity())
    {
        size_t newcapacity = size()==0?4:capacity()*2;  //需要考虑到size是否有可能为0的情况
        reserve(newcapacity);
    }
    *_finish = val;
    _finish++;
}

void pop_back()
{
    assert(size()>0);
    _finish--;
}

iterator insert(iterator pos,const T& val)
{
    assert(pos>=_start && pos <= _finish);
    if(_finish == _end_of_storage)
    {
        int n = pos - _start;
        size_t newcapacity = 0 ? 4 :capacity()*2;
        pos = _start + n;      //防止pos迭代器失效
    }
    iterator cur = end();
    while(cur > pos)
    {
        *cur = *(cur-1);
        cur--;
    }
    *pos = val;
    _finish++;
    return pos;
}

iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    iterator it = pos + 1;
    while (it != _finish)
    {
        *(it-1) = *it;
        ++it;
    }
    --_finish;
    return pos;
}

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
    reserve(v.capacity());
    for (const auto& e : v)
    {
        push_back(e);
    }
}

T& operator[](size_t i)
{
    assert(i < size());
    return _start[i];
}
const T& operator[](size_t i) const
{
    assert(i < size());
    return _start[i];
}

vector<T>& operator=(vector<T> v)    //注意哦~,我这里故意写的传值参数,而不是引用,是为了下面进行交换
{
    swap(*this,v);
    return *this;
}

int main()
{
    //我们假设最开始创建的vector的容量是4
	vector<string> vc;
	vc.push_back("123");    //创建vc,并给其赋值
    vc.push_back("234");
    vc.push_back("345");
    vc.push_back("456");
    vc.push_back("567");
    return 0;
}

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];               //先开辟一块空间
        size_t sz = size();              //保留原来的有效数据大小,且一定要先保存
        if (_start)        //一定要判断这个,因为最开始_start为空,那么就只需要开空间
        {
            memcpy(tmp, _start, sizeof(T) * n);  //把原来的数据拷贝进新空间
            delete _start; //释放原来的空间
        }
        _start = tmp;                    //移交空间
        _finish = _start + sz;           //更新_finish
        _end_of_storage = _start + n;    //更新_end_of_storage
    }
}

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t sz = size();
        T* tmp = new T[n];
        if (_start)
        {
            for (size_t i = 0; i < sz; ++i)
            {	
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _endofstorage = _start + n;
    }