C++ vector类模拟实现

上一篇讲解了vector的使用，这一篇接着介绍vector的模拟实现，这里依然是讲解常用接口的模拟实现，话不多说，正文开始！

1. 成员变量

vector的成员变量是三个指针

namespace sakura    //命名空间
{
   
   
    template<class T>
    class vector
    {
   
   
    public:
        typedef T* iterator; //迭代器
        typedef const T* const_iterator;
    private:
        iterator _start; //指向已开辟空间起始位置
        iterator _finish; //指向有效元素的下一个位置
        iterator _end_of_storage; //指向已开辟空间的下一个位置
    };
}

我们使用vector存储的数据类型会是int、char等不同的类型，使用模板可以更好的实例化

2. 默认成员函数

2.1 构造和析构

==构造函数==

//默认构造
vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_storage(nullptr)
{
   
   }
//带参构造
vector(size_t n, const T& val = T()) //const T&修饰匿名对象->起别名延长生命周期
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
   
   
    reserve(n);
    for (size_t i = 0; i < n; ++i)
    {
   
   
        push_back(val);
    }
}
//此版本避免匹配迭代器区间构造
vector(int n, const T& val = T()) //const T&修饰匿名对象->起别名延长生命周期
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
   
   
    reserve(n);
    for (int i = 0; i < n; ++i)
    {
   
   
        push_back(val);
    }
}
//迭代器区间构造 左闭右开[first, last)
template<class InputIterator>
vector(InputIterator first, InputIterator last) 
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
   
   
    while (first != last)
    {
   
   
        push_back(*first);
        ++first;
    }
}

这里vector(size_t n, const T& val = T())使用了匿名对象做缺省值

• 匿名对象的生命周期只在本行有效，但其被const修饰后生命周期会延长
• 内置类型也能创建匿名对象，如int()、char()

注意： 这里需要额外提供一个 vector(int n, const T& value = T()) 版本，避免使类似vector<int> v(6, 8) 构造对象会优先匹配上迭代器构造，造成 *非法间接寻址错误

==析构函数==

~vector()
{
   
   
    delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
}

_start 指向的是已开辟空间的首位置，可以直接对其释放，由于申请空间用的是new []，所以释放时需要对应使用delete []

2.2 拷贝和赋值

==拷贝构造==

拷贝构造对象前先进行扩容，避免空间浪费，这里采用逐个数据赋值拷贝的方式，因为 T 有可能是自定义类型，这样可以避免浅拷贝问题

vector(const vector<T>& v)
    :vector() //使用默认构造初始化
{
   
   
    reserve(v.capacity());    //扩容
    _start = new T[v.capacity()];
    //memcap(_start, v._start, sizeof(T) * v.size()); //浅拷贝，err
    for (size_t i = 0; i < v.size(); ++i)
    {
   
   
        _start[i] = v._start[i];
    }
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();
}

这里不能采用memcpy来进行拷贝操作，因为memcpy是浅拷贝

vector的拷贝构造必须自己实现，默认生成的是浅拷贝

==赋值重载==

赋值重载的实现和拷贝构造差不多，只是不需要新对象，只需进行赋值操作即可

vector<T>& operator=(const vector<T>& v)
{
   
   
    if (this != &v)
    {
   
   
        reserve(v.capacity());    //扩容
        size_t pos = 0;
        for (size_t i = 0; i < v.size(); ++i)
        {
   
   
            *(_start + i) = *(v.begin() + i)
        }
        _finish = begin() + v.size();
    }
    return *this;
}

3. 容量操作

3.1 查看容量大小和判空

可以直接通过迭代器操作获取所需值

size_t capacity() const
{
   
   
    return _end_of_storage - _start;
}

size_t size() const
{
   
   
    return _finish - _start;
}

bool empty()
{
   
   
    return _start == _finish;
}

3.2 reserve方法

操作步骤：

• 判断是否需要扩容
• 拷贝数据，保存有效元素大小
• 开辟新空间，将拷贝的数据移动至新空间，然后释放旧空间，更改指针指向

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;
        _end_of_storage = _start + n;
    }
}

先保存有效元素大小这一步很重要！！！

因为size() = _finish - _start，所以_finish = _start + size()，再代入size()就造成了_finish = _start + _finish - _start --> _finish = _finish恒等式

3.3 resize方法

操作步骤：

• 判断n与size()的大小
• 如果n < size()就删除超出数据，反之就插入

void resize(size_t n, T val = T())
{
   
   
    if (n < size())
    {
   
   
        //删除数据
        _finish = _start + n;
    }
    else
    {
   
   
        if (n > capacity())
            reserve(n);
        while (_finish != _start + n)
        {
   
   
            *_finish = val;
            ++_finish;
        }
    }
}

4. 数据访问

4.1 下标访问

下标访问就是operator[]重载

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

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

4.2 迭代器

vector中的迭代器使用的是原生指针，如 begin() == _start、end() == _finish，这里需要提供普通版本和const版本的两种迭代器

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;
}

5. 数据修改

5.1 push_back方法

尾插要注意首先判断容量是否足够，然后插入数据改变_finish指向即可

void push_back(const T& x)
{
   
   
    if (_finish == _end_of_storage)
    {
   
   
        reserve(capacity() == 0 ? 4 : capacity() * 2);
    }
    *_finish = x;
    ++_finish;
}

5.2 pop_back方法

尾删需要先判断容器中是否有数据，然后直接该变_finish指向即可

void pop_back()
{
   
   
    assert(!empty());
    --_finish;
}

5.3 insert方法

iterator inseret(iterator pos, const T& val)
{
   
   
    assert(pos >= _start);
    assert(pos <= _finish);
    if (_finish == _end_of_storage)
    {
   
   
        size_t len = pos - _start; //记录当前迭代器的位置（pos和_start间的距离）
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        //扩容后更新pos，解决pos失效问题
        pos = _start + len;
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
   
   
        *(end + 1) = *end;
        --end;
    }
    *pos = val;
    ++_finish;
    return pos;
}

==注意：==

insert()的实现中，一定要先记录pos的位置，因为在扩容后迭代器pos的位置会指向已释放的旧空间，导致迭代器失效！

迭代器失效演示：

改进方法：

5.4 erase方法

iterator erase(iterator pos)
{
   
   
    assert(pos >= _start);
    assert(pos < _finish);
    //迭代器区间删除
    iterator start = pos + 1;
    while (start != _finish)
    {
   
   
        *(start - 1) = *start;
        ++start;
    }
    --_finish;
    return pos;
}

visual studio2019中的erase机制是一定会pos迭代器失效

6. 完整代码

#pragma once

#include <iostream>
#include <vector>
#include<assert.h>
#include <functional>
#include<algorithm>
#include<vector>
using namespace std;

namespace sakura
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

        //默认构造
        vector()
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {}
        //带参构造
        vector(size_t n, const T& val = T()) //const T&修饰匿名对象->起别名延长生命周期
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {
            reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }
        //此版本避免匹配迭代器区间构造
        vector(int n, const T& val = T()) //const T&修饰匿名对象->起别名延长生命周期
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }
        //迭代器区间构造 左闭右开[first, last)
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        vector(size_t n, const T& val = T())
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

        vector(int n, const T& val = T())
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

        vector(const vector<T>& v)
            :vector() //使用默认构造初始化
        {
            reserve(v.capacity());    //扩容
            _start = new T[v.capacity()];
            //memcap(_start, v._start, sizeof(T) * v.size()); //浅拷贝，err
            for (size_t i = 0; i < v.size(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();
        }

        ~vector()
        {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }

        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        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;
                _end_of_storage = _start + n;
            }
        }

        void resize(size_t n, T val = T())
        {
            if (n < size())
            {
                //删除数据
                _finish = _start + n;
            }
            else
            {
                if (n > capacity())
                    reserve(n);
                while (_finish != _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }

        void push_back(const T& x)
        {
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }

        void pop_back()
        {
            assert(!empty());
            --_finish;
        }

        iterator inseret(iterator pos, const T& val)
        {
            assert(pos >= _start);
            assert(pos <= _finish);
            if (_finish == _end_of_storage)
            {
                size_t len = pos - _start; //记录当前迭代器的位置（pos和_start间的距离）
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                //扩容后更新pos，解决pos失效问题
                pos = _start + len;
            }
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = val;
            ++_finish;
            return pos;
        }

        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos < _finish);
            //迭代器区间删除
            iterator start = pos + 1;
            while (start != _finish)
            {
                *(start - 1) = *start;
                ++start;
            }
            --_finish;
            return pos;
        }

        size_t capacity() const
        {
            return _end_of_storage - _start;
        }

        size_t size() const
        {
            return _finish - _start;
        }

        bool empty()
        {
            return _start == _finish;
        }

        vector<T>& operator=(const vector<T>& v)
        {
            if (this != &v)
            {
                reserve(v.capacity());    //扩容
                size_t pos = 0;
                for (size_t i = 0; i < v.size(); ++i)
                {
                    *(_start + i) = *(v.begin() + i)
                }
                _finish = begin() + v.size();
            }
            return *this;
        }

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

        const T& operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }
    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };

    void func(const vector<int>& v)
    {
        for (size_t i = 0; i < v.size(); ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;

        vector<int>::const_iterator it = v.begin();
        while (it != v.end())
        {
            cout << *it << " ";
            it++;
        }
        cout << endl;
    }
}

C++【STL】之vector模拟实现，到这里就介绍结束了，本篇文章对你由帮助的话，期待大佬们的三连，你们的支持是我最大的动力！

文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正！