『C++成长记』vector模拟实现

namespace bit
{
    template<class T> //模板参数T
    class vector
    {
    public:
        typedef T* iterator;		//指针重命名为迭代器
        typedef const T* const_iterator;
    private:
        iterator _start; 
        iterator _finish; 
        iterator _end_of_storage; 
	}；
}

_start：指向空间的起始地址
_finish：指向最后一个数据的下一个地址，相当于_size
_end_of_stroage：指向空间最后一个最末地址,相当于_capacity

小Tips：由于vector使用了模板，所以函数实现都在头文件中，防止因为模板导致的链接错误的问题！

二、默认成员函数

📒2.1构造函数

我们在这里实现三个版本，分别是：默认构造函数，带参构造函数和迭代器区间构造。

默认构造函数：初始化三个指针置空即可
带参构造函数：初始化n个T类型的value值在对象中
迭代器区间构造：通过其他容器迭代器或指针迭代插入其所有值

//默认构造函数
vector()
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{}

vector () = default //强制编译器生存默认构造

//构造n个T类型数据
vector(size_t n, const T& value = T()) 
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    reserve(n);
    for (int i = 0; i < n; ++i)
    {
        *(_finish++) = value;
    }
}

//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    while (first != last) //迭代器插入数据
    {
        push_back(*first);
        ++first;
    }
}

注意：我们实现了带参构造函数的n为size_t类型的版本，如果我们使用带参构造函数实例化，则会发生非法间接寻址的错误！这是因为size_t是整型，实例化T数据类型也是整型，此时编译器会自动匹配最合适的构造函数，于是匹配到了迭代器区间构造。我们只要写一个n为int类型的带参构造参数去匹配，就可以解决问题。

📒2.2拷贝构造

对于拷贝构造我们要考虑深浅拷贝的问题，我们希望当一个vector对象拷贝另一个对象时新对象开辟新的空间拷贝数据，而不是两个对象共用同一块空间，否则会析构两次造成内存泄漏。

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

📒2.3赋值重载

赋值重载与拷贝构造的问题类似，也要注意深拷贝问题；区别于拷贝构造的地方在于不需要新建对象，但是需要判断是否为同一个对象避免重复开空间。

//传统写法
vector<T>& operator=(const vector<T>& v)
{
    if (&v != this) 
    {
        clear(); 
        reserve(v.capacity()); 
        for (int i = 0; i < v.size(); ++i)
		{
            *(_finish++) = v._start[i]; 
        }
    }
    return *this;
}

//现代写法
void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}

// v1 = v3
vector<T>& operator=(vector<T> v)
{
    swap(v);
    return *this;
}

三、容量操作

📒3.1获取有效元素个数

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

📒3.2获取空间容量大小

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

小Tips：vevtor是使用3个指针对空间进行管理，使用_finish(有效数据指针)减去_start(空间首地址)就能得出有效数据个数，容量同理。我们只是对数据进行访问不涉及修改，所以使用const修饰this指针。

📒3.3使用reverse扩容

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t oldsize = size();//获取扩容前有效数据个数
        T* tmp = new T[n];
        if(_start)
        {
            //memcpy(tmp, _start, sizeof(T*) * size());
            for (size_t i = 0; i < oldsize; i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + oldsize;
        _end_of_storage = _start + n;
    }
}
//错误写法：_finish = _start + size() ；

小Tips：我们要用oldsize记录扩容前有效数据的个数，按照错误写法size()是用扩容前的_finish和扩容后的_start来计算的，结果是错误的。当string类型的对象要扩容时，memcpy对数据进行的是浅拷贝，两个对象指向同一块空间，会析构两次造成内存泄漏。

四、数据访问

📒4.1下标访问

下标访问是通过重载 [ ] 运算符实现的，在下标pos正确的情况下，返回当前下标字符的引用，否则assert报错。

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

const T& operator[](size_t pos) const //const引用版本,不可以修改
{
    assert(pos < size()); 
    return _start[pos];
}

at 函数我们可以复用运算符[ ]来实现。 at 函数的检查手段是抛异常。

T& at(size_t pos) 
{ 
    return (*this)[pos]; 
}

const T& at(size_t pos) const 
{ 
    return (*this)[pos]; 
}

📒4.1迭代器访问

typedef T* iterator;
typedef const T* const_iterator;

const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

iterator begin() { return _start; }
iterator end() { return _finish; }

//范围for
for (auto e : v1)
{
    cout << e << " ";
}
cout << endl;

五、修正操作

📒5.1尾插数据

在尾插前检查容量是否充足，空间不够扩容，然后直接插入_finish的空位下即可，_finish指针移动到下一个空位。

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

    //insert(end(), x);    //复用
}

📒5.2尾删数据

尾删只需要--_finish，但需要判断size是否>0。

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

📒5.3在任意位置插入数据

当我们传递一个迭代器在pos位置插入数据时，可能涉及容器扩容，如果扩容，那么迭代器是旧空间的迭代器，则会导致迭代器失效，因为原有空间已经被释放，但迭代器还是指向原空间(那么就是野指针)，所以我们在插入或删除后要更新迭代器。

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);
    if (_finish == _end_of_storage)
    {
        size_t len = pos - _start;
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
        pos = _start + len;
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    _finish++;
    return pos;
}

小Tips：如果要进行扩容我们用len来记录扩容前从_start到pos位置数据的个数，然后扩容后更新pos的位置。

📒5.4在任意位置删除数据

删除元素也会有迭代器失效的问题，可能会越界访问。

iterator earse(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);
    iterator it = pos + 1;
    while (it != _finish)
    {
        *(it - 1) = *it;
        it++;
    }
    --_finish;
    return pos;    //返回删除元素位置的下一个元素的迭代器
}

🎁结语：

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。

原文地址:https://blog.csdn.net/2301_76207836/article/details/138250559 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1811976857134960640.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部