c++ vector模拟实现

一、vector是什么?

vector是表示可变大小数组的序列容器,它也采用连续存储空间来存储元素,因此可以采用下标对vector的元素进行访问,它的大小是动态改变的,vector使用动态分配数组来存储它的元素;

二、容器特性

1.顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素;

2.动态数组

支持对序列中的任意元素进行快速直接访问,甚至可以通过指针进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作;

3.能够感知内存分配器的

容器使用一个内存分配器对象来动态地处理它的存储需求;

三、vector的模拟实现

  • 定义一个类:
template<class T>
class Vector
{
    T* _start; //首元素地址
    T* _finish; //最后一个元素地址的下一个地址
    T* _endOfStorage; //空间的尾地址
public:
//成员函数
};
  • 构造函数
Vector()
    :_start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
{}

Vector(size_t n, const T& value = T())
    :_start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
{
    reserve(n);
    while (n--)
    {
        push_back(value);
    }
}
Vector(InputInterator first, InputInterator last)
        :_start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        while (first != last)
        {
            pushBack(*first);
            ++first;
        }
    }
  • 数据大小、空间大小
size_t size() const
{
    return _finish - _start;
}

size_t capacity() const
{
    return _endOfStorage - _start;
}
  • 尾插
void pushBack(const T& value)
    {
        if (_finish == _endOfStorage)
        {
            size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
            reverse(value);
        }
        *_finish = value;   
        ++_finish;
    }
  • 扩容

    有资源进行拷贝时,使用深拷贝;类型为自定义类型时,发生浅拷贝,调用自定义类型析构函数,释放资源,导致资源二次释放,所以自定义类型的拷贝有资源时进行深拷贝;

    void reserve(size_t n)
    {
    if (n &gt; capacity())
    {
    size_t sz = size();
    T* arr = new T[n];
    if (_start)
    {
    memcpy(arr, _start, sizeof(T) * sz);
    delete[] _start;
    }
    //update
    _start = arr;
    _finish = _start + sz;
    _endOfStorage = _start + n;
    }
    }
  • 改变数据大小
void resize(size_t n, const T& val = T())
    {
        if (n > capacity())
        {
            reserve(n);
        }
        else if (n > size())
        {
            while (_finish != _start + n)
            {
                *_finish = val;
                _finish++;
            }
        }
            _finish = _start + n;
    }
  • 位置插入值
void insert(iterator pos, const T& val)
    {
        size_t sz = pos - _start;
        //检查位置
        if (pos >= _start && pos <= _finish)
        {
            //检查容量
            if (_finish == _endOfStoage)
            {
                size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();               
                reserve(n);
                //更新迭代器
                pos = _start + sz;
            }
            //移动元素
            iterator end_u = _finish;
            while (end_u != pos)
            {
                *end = *(end_u - 1);
                --end_u();
            }
            //插入元素
            *pos = val;
            //更新位置
            ++_finish;
        }
    }
  • 删除数据
iterator erase(iterator pos)
    {
        //检查位置
        if (pos < _finish && pos >= _start)
        {
            //移动元素
            iterator start = pos + 1;
            while (start!=_finish)
            {
                *(start - 1) = *start;
                start++;
            }
            //更新
            --_finish;
        }
        return pos;
    }
    //返回删除数据的下一个元素的位置
  • operator[] 重载
T& operator[](size_t pos)
    {
        if (pos >= 0 && pos < size())
            return _start[pos];
    }
  • operator= 重载
    Vector<T>& operator=(const Vector<T>& v)
    {
        if (this != &v)
        {
            delete[]_start;
            size_t n = v.capacity();
            _start = new T[n];
            for (size_t i = 0; i < v.capacity(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _finish = _start + n;
        }
        return *this;
    }
  • 迭代器
//vector迭代器:T*
typedef T* iterator;
typedef const T* const_iterator;

iterator begin()
{
    return _start;
}

iterator end()
{
    return _finish;
}

const_iterator begin() const
{
    return _start;
}

const_iterator end() const
{
    return _finish;
}
  • 析构函数
~Vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }
}
上一篇:力扣104. 二叉树的最大深度


下一篇:Leetcode 897. 递增顺序搜索树