【STL】模拟实现vector（详解）网站首页 技术交流

【STL】模拟实现vector（详解）

迷茫的启明星 2024-06-14 17:17:59

简介【STL】模拟实现vector（详解）

前言

本文将讲述怎么模拟实现vector类，有些同学可能会问了，我要实现这个有什么用？会用不就可以了吗？

你没有错，但是我们通过模拟实现vector类可以帮助我们更加深入的了解它具体是怎么一回事？它的内部结构是怎么样的？如果以后我们写程序，碰到某个地方报错，也能很快排查出问题哦~

?作者：迷茫的启明星
专栏：《C++初阶》

?欢迎关注：?点赞?收藏✍️留言

?码字不易，你的?点赞?收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！

持续更新中~

vector的模拟实现

一，搭建框架

我们首先把大概框架搭建出来，就像打铁，要先打个大概的模子再细细锤炼，它和string的不同在于，vector 是基于连续内存的动态数组，而 string 可以是基于指针或数组的动态字符序列，所以vector 的成员函数是三个指针：指向数组的指针 start_、指向最后一个元素的下一个位置的指针 finish_，以及指向整个内存空间末尾的指针 end_of_storage_。那么我们现在就来搭建一下：

#pragma once
#include <assert.h>

namespace hxq
{
	template<class T>
    //这里要用模板，因为数组不只有一种类型
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		iterator begin()
		{
			return _start;//返回首元素位置的指针
		}

		iterator end()
		{
			return _finish;//返回最后一个元素下一个位置的指针
		}
		//const类型
		const_iterator begin() const
		{
			return _start;//返回首元素位置的指针
		}

		const_iterator end() const
		{
			return _finish;//返回最后一个元素下一个位置的指针
		}
        
		~vector()//析构函数，释放资源
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

		size_t capacity() const
		{
            //返回vector空间大小
			return _end_of_storage - _start;
		}

        //const类型
		const T& operator[](size_t pos) const
		{
            //用于访问指定位置上的元素
            
			assert(pos < size());

			return _start[pos];
		}

		T& operator[](size_t pos)
		{
            //用于访问指定位置上的元素
            
			assert(pos < size());

			return _start[pos];
		}
		//返回vector的元素数量
		size_t size() const
		{
			return _finish - _start;
		}
        
		//返回第一个元素
		T& front()
		{
			assert(size() > 0);

			return *_start;
		}

        //返回最后一个元素
		T& back()
		{
			assert(size() > 0);

			return *(_finish - 1);
		}

	private:
		iterator _start;//指向数组的指针
		iterator _finish;//指向最后一个元素的下一个位置的指针
		iterator _end_of_storage;//指向整个内存空间末尾的指针
	};
}

二，实现构造函数

vector的构造函数非常简单，因为成员变量都是指针，所以我们只要将它们置空即可。

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

三，构造的其他方式

和我们实现string一样，vector也有传统1写法和现代写法，他们实现的效果是一样的，不过是思维不一样而已，那么我们再来一起尝试写一写两种方式。

传统写法

1.拷贝构造

假设说是v1(v2)

步骤：

给v1开辟新空间
将v2的值按位拷贝给v1
将成员变量更新

所以我们可以这样写：

vector(const vector<T>& v)
{
    _start = new T[v.size()]; // v.capacity()也可以
    //这里还可以复用reserve函数，后面我们再实现它
    
    //思考题：
    //思考一下这里我们可以这样写吗？
    //memcpy(_start, v._start, sizeof(T)*v.size());
    
    for (size_t i = 0; i < v.size(); ++i)
    {
        _start[i] = v._start[i];
    }
    
    
    _finish = _start + v.size();
    _end_of_storage = _start + v.size();
}

思考题答案是不能

在实现vector拷贝构造函数时，使用memcpy是一种浅拷贝，它仅仅是复制了vector对象的数据成员_start所指向的内存区域，而没有复制_start所指向的数组中的每个元素内容。这意味着，如果原始vector发生变化，则新的vector也会受到影响，导致两个vector共享同一个数组。这样就会出现问题，当其中一个vector执行析构函数时，可能会释放已经被释放的内存区域，导致程序崩溃。

因此，为了避免这种问题，我们需要对vector的每个元素进行逐个拷贝，以实现深度拷贝。因此，上述代码采用了for循环来依次拷贝每个元素的方式，确保了新的vector与原始vector具有独立的数组空间和元素值。

拷贝构造还可以这样写，复用之后我们实现的函数实现。

vector(const vector<T>& v)
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_storage(nullptr)
    {
        reserve(v.size());//设置空间
        for (const auto& e : v)
        {
            push_back(e);//尾插
        }
    }

我们先能看懂大概意思就好，后面会一一实现这些函数的。

这里我们先将其初始化，再调用函数给它分配空间，调用函数插入数据（也就是拷贝数据了）。

2. 重载赋值操作符

假设是v1=v2

思路：

直接利用另一个 vector 对象的值。在函数内部使用 swap() 函数交换了两个 vector 对象的 _start、_finish 和 _end_of_storage 成员变量，从而将右侧的 vector 对象中的数据成员拷贝到了当前对象中，完成了赋值操作
为什么可以？因为它是传值，所以不影响原对象

vector<T>& operator=(vector<T> v)
{
    swap(v._start, _start);
    swap(v._finish, _finish);
    swap(v._end_of_storage, _end_of_storage);
    return *this;
}

3. 使用迭代器构造

当我们需要构造一个包含一定数量元素的 vector 对象时，可以使用 vector 的构造函数。其中，vector(InputIterator first, InputIterator last) 构造函数接受一对迭代器 [first, last) 作为参数，用于指定需要添加到 vector 中的元素范围。构造函数的实现方式是遍历迭代器范围，每次调用 push_back() 函数将迭代器指向的元素添加到当前 vector 对象的末尾。

需要注意的是，在构造函数中，vector 的 _start、_finish 和 _end_of_storage 成员变量都被设置为 nullptr，表示当前 vector 对象还没有分配任何内存空间。在循环遍历迭代器范围时，每次添加元素时，vector 内部的内存管理函数会自动动态地分配内存空间，并将新的元素存储在这个空间中。当元素个数超过了当前内存空间的大小时，vector 会自动扩充内存空间，以满足新增元素的需求。

	template <class InputIterator>
    vector(InputIterator first, InputIterator last)
    	:_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {
        while(first != last)
        {
            push_back(*first);
            ++first;
        }
    }

4. 初始化为N个val的vector

还有一种初始化方式是初始化为N个val的vector，它需要两个参数，一是数量n，二是val，这里实现时要注意的是，我们要考虑的不只是一种类型，所以这里要用到模板相关知识。

具体实现就简单多了，这只需要先初始化再申请空间，将val的值利用push_back函数插入即可，可能你会问：“为什么老是用这些函数？不自己再实现一遍呢？”，我们要注意的是，这些函数后文我们都会再实现的，但是这里为什么要用函数呢？是为了复用,你想想，要是我们写的代码中有一堆功能相似的代码，是不是屎山代码，极其不美观？我们要尽量避免大量重复代码这种情况。

vector(size_t n, const T& val = T())
    :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {
        reserve(n);
        for (size_t i = 0; i < n; ++i)
        {
            push_back(val);
        }
    }

现代写法

1. 拷贝构造

还有一种现代写法
这是一种有着资本主义或者说老板思维，让员工干活
具体怎么回事呢？
v2(v1)
我们可以新建一个vector对象,并且以nullptr来初始化它
的三个成员变量，然后再新建一个空间，这个新的空间以v1的值、以迭代器的方式初始化，再使用swap函数交换而获取到它的数据。

void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}
vector(const vector<T>& v)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}

2. 赋值重载

和传统写法一样，不过这里可以复用前面的swap函数

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

四，实现vector相关函数

1. reserve函数

在 C++ 的 vector 中，reserve(size_type n) 是一个用于预留内存空间的函数。

具体来说，reserve() 函数接受一个参数 n，代表需要预留的内存空间大小。在调用 reserve() 函数后，vector 内部会分配一块大小为 n 的内存空间，但不会改变 vector 的元素个数（即 size() 函数返回值不受影响）。这意味着，我们可以通过 reserve() 函数提前为 vector 分配足够的内存空间，以避免频繁的动态扩容操作，从而提高程序的性能。

需要注意的是，尽管 reserve() 函数为 vector 分配了一定大小的内存空间，但并不意味着这些内存空间都被包含在 vector 的有效元素范围内。只有当这些内存空间真正被添加到 vector 对象中时，它们才被视为 vector 对象的一部分。因此，在调用 reserve() 函数后，如果需要使用新的内存空间，则应该通过 push_back()、insert() 等函数添加元素，从而将新的元素存放到 vector 对象中。

需要注意的是：我们应该根据实际情况慎重考虑应该预留多少内存空间，以避免过度浪费内存资源。

实现思路：

首先判断传入的参数是否大于已有空间
需要扩容则开辟一块新的空间
将所有元素拷贝到新空间
再将成员变量更新

这里有个问题，将所有元素拷贝到新空间可以用memcpy函数吗？

回顾一下memcpy函数的使用：

当调用 memcpy() 函数时，它会将从源内存地址开始的 n 个字节的数据拷贝到目标内存地址中，也就是从 src 所指向的内存地址开始的 n 个字节的数据会被拷贝到 dest 所指向的内存地址中。

所以我们能使用它来拷贝数据吗？仔细思考就会发现，它不完全符合条件。

std::vector 对象的内部存储结构是动态分配的，对其使用 memcpy() 拷贝时可能会出现未定义行为。

std::vector 是 C++ 标准库提供的容器之一，它除了存储元素外还有管理容器大小、元素添加和移除等操作。使用 memcpy() 会绕过 std::vector 对象自身的管理和维护，可能会导致程序出现异常或者崩溃。

std::vector 可能包含自定义类型的元素，而这些元素可能包含指针等资源，需要进行深拷贝才能正确复制。如果使用 memcpy() 直接拷贝内存，就无法正确处理这些元素的拷贝。

具体怎么回事？

在 C++ 中，std::vector 可以存储任意类型的元素。当这些元素是自定义类型时，往往会包含指针等资源。例如：
struct point {
    int x;
    int y;
};

struct line {
    point* p1;
    point* p2;
};
在上面的代码中，我们定义了 point 和 line 两个结构体，其中 line 的成员变量 p1 和 p2 是指向 point 类型对象的指针。如果我们将 line 对象作为元素插入到 std::vector 容器中，那么这个容器就包含了指向堆内存中的 point 对象的指针。

当我们需要对 std::vector 容器进行拷贝操作时，如果直接对容器中的指针进行拷贝，就直接复制了指针的值，而没有复制指针所指向的对象。也就是说，新的 std::vector 容器中的元素指向的是旧的 std::vector 容器中的元素所指向的对象，造成两个 std::vector 容器共享同一块堆内存，无法正确地实现拷贝。

为了解决这个问题，需要对包含指针等资源的自定义类型进行深拷贝。深拷贝是一种将指针所指向的对象也复制一份的拷贝方式，以确保新的对象与旧的对象相互独立，不会共享同一个资源。对于包含指针等资源的自定义类型，可以通过重载拷贝构造函数和赋值运算符，或者使用智能指针等方法进行深拷贝。但是，这些方法不能与 memcpy() 函数兼容，如果直接使用 memcpy() 函数会导致指针指向错误的内存地址，无法正确地完成拷贝操作。

而且，在 C++ 中，std::vector 是一个动态数组容器，它使用动态分配的内存来存储元素。当我们向 std::vector 容器中添加元素时，如果容器已经占满了当前的内存空间，就会自动重新分配更大的内存，并将原有的元素复制到新的内存空间中。这个过程称之为“重新分配”（re-allocation）。

在重新分配内存时，std::vector 会自动调用元素类型的构造函数来构造新的元素对象，并调用元素类型的析构函数来销毁旧的元素对象。这个过程会保证 std::vector 容器中的元素始终是合法的、可访问的对象。

如果对 std::vector 使用 memcpy() 函数进行拷贝操作，由于 memcpy() 只会简单地复制一段内存的内容，不会触发任何构造函数或析构函数的调用，从而导致拷贝出的容器中的元素对象处于不合法的状态。这样的拷贝结果是未定义的，可能会导致程序运行出错、崩溃、甚至安全问题，因此不建议使用 memcpy() 来进行 std::vector 的拷贝操作。

代码：

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

2，resize函数

在 C++ 中，std::vector 容器提供了 resize() 函数来改变容器的大小。该函数接受一个整型参数 newSize，表示容器调整后的大小。如果当前容器大小小于 newSize，则会在容器尾部插入一定数量的元素来扩充容器大小；如果当前容器大小大于 newSize，则会删除容器尾部的一定数量的元素来缩小容器大小。

具体来说，当 newSize 小于当前容器大小时，resize() 会将末尾多余的元素删除，释放内存空间；当 newSize 大于当前容器大小时，resize() 会在末尾插入必要数量的元素，并分配更多的内存空间。

代码：

void resize(size_t n, const T& val = T())
{
    if (n > capacity())
    {
        reserve(n);//如果空间少了就申请空间
    }

    if (n > size())
    {
        // 初始化填值
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else
    {
        _finish = _start + n;
    }
}

3，push_back函数

在C++中，std::vector是一个动态数组容器，其大小可以动态地增加或减少。我们可以使用 push_back()函数向 std::vector 容器的尾部添加元素。

push_back() 函数接受一个参数，表示需要添加到容器尾部的元素值，该函数会将元素添加到容器的末尾，并自动调整容器的大小。如果容器已经占满了目前已分配的内存空间，那么会自动申请更多的内存空间，并将原来的元素对象移动到新的空间中保存。

它可以使用两种方式实现：

自给自足

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

    *_finish = x;
    ++_finish;
}

复用insert函数

void push_back(const T& x)
{
    insert(end(), x);
}

4，pop_back函数

在C++中，std::vector 是一个动态数组容器，其大小可以动态地增加或减少。我们可以使用 pop_back() 函数从 std::vector 容器的尾部移除元素。

pop_back() 函数没有参数，它将从容器尾部移除一个元素。如果容器不为空，那么该函数会将容器的大小减少 1，并将最后一个元素对象从容器中销毁，释放内存空间。

思路：

这里我们可以不需要去删除元素，只要控制_finish的位置即可

代码：

void pop_back()
{
    assert(_finish > _start);
    --_finish;
}

5，insert函数

std::vector 是 C++ 标准库中的一个容器，可以快速、高效地对一组元素进行动态数组式的操作。其中，insert 函数是 std::vector 容器提供的一个成员函数，用于在指定位置插入一个或多个元素。

这里我们仅实现插入一个元素的函数

思路：

insert函数是用来在 std::vector 容器的任意位置插入一个新元素的函数。在该函数中，我们需要传入两个参数，分别是迭代器 pos 和元素 x。

首先，我们需要通过迭代器找到要插入新元素的位置。对于 std::vector 容器而言，迭代器类型为 T*，即指向存储容器元素的指针。该函数的第一个参数 pos 就是要传入指向容器中某个元素的指针，表示将新元素插入到该元素前面或后面。

接下来，我们需要指定要插入的新元素的类型。由于 std::vector 容器中所有元素类型必须相同，因此我们使用模板参数 T 来表示要插入元素的类型，并将其定义为 const T& 常量引用。

最后，使用内部实现逻辑，我们可以通过比较迭代器 pos 和 _start、_finish、_end_of_storage 三个指向容器起始、末尾和存储空间末尾位置的指针来确认 pos 的位置是否合法，从而防止越界访问或插入。然后，我们将新元素插入到指定位置，将原先位置及其后面的元素向后移动一位。

这样，我们就可以在 std::vector 容器中的任意位置插入一个新元素，从而添加、修改或更新容器中的元素。

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    if (_finish == _end_of_storage)
    {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
    }

    // 挪动数据
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;

    ++_finish;

    return pos;
}

6，erase函数

std::vector 是 C++ 标准库中的一个容器，可以快速、高效地对一组元素进行动态数组式的操作。其中，erase 函数是 std::vector 容器提供的另一个成员函数，用于删除指定位置或一段区间内的一个或多个元素。

这里我们仅实现删除一个元素的函数

思路：

在 STL 中，erase 函数返回的是指向被删除元素之后的一个元素的迭代器，而不是指向被删除元素的迭代器。这种设计是考虑到 erase 函数的常见用法，即在循环中删除符合条件的元素。

在这种情况下，如果返回指向被删除元素的迭代器，那么在执行 erase 操作后，迭代器会失效，即无法正常访问和操作，进而导致循环出错甚至崩溃。因此，STL 设计者规定返回指向被删除元素之后的一个元素的迭代器，避免使用已经失效的迭代器。

代码：

iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator begin = pos + 1;
    while (begin < _finish)
    {
        *(begin - 1) = *begin;
        ++begin;
    }

    --_finish;
    return pos;
}

源码

#pragma once
#include <assert.h>
#include <iostream>
namespace hxq
{
    template<class T>
        class vector
        {
            public:
            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()
                :_start(nullptr)
                    , _finish(nullptr)
                    , _end_of_storage(nullptr)
                {}
            //传统写法
            //拷贝构造
            // v2(v1)
            //        vector(const vector<T>& v)
            //        {
            //        	_start = new T[v.size()]; // v.capacity()也可以
            //        	//memcpy(_start, v._start, sizeof(T)*v.size());
            //        	for (size_t i = 0; i < v.size(); ++i)
            //        	{
            //        		_start[i] = v._start[i];
            //        	}
            //        	_finish = _start + v.size();
            //        	_end_of_storage = _start + v.size();
            //        }

            // v2(v1)
            //        vector(const vector<T>& v)
            //            :_start(nullptr)
            //            , _finish(nullptr)
            //            , _end_of_storage(nullptr)
            //        {
            //            reserve(v.size());
            //            for (const auto& e : v)
            //            {
            //                push_back(e);
            //            }
            //        }
            //初始化为N个val
            vector(size_t n, const T& val = T())
                :_start(nullptr)
                    , _finish(nullptr)
                    , _end_of_storage(nullptr)
                {
                    reserve(n);
                    for (size_t i = 0; i < n; ++i)
                    {
                        push_back(val);
                    }
                }
            //使用迭代器构造
            template <class InputIterator>
                vector(InputIterator first, InputIterator last)
                :_start(nullptr)
                    , _finish(nullptr)
                    , _end_of_storage(nullptr)
                {
                    while(first != last)
                    {
                        push_back(*first);
                        ++first;
                    }
                }
            //现代写法
            void swap(vector<T>& v)
            {
                std::swap(_start, v._start);
                std::swap(_finish, v._finish);
                std::swap(_end_of_storage, v._end_of_storage);
            }

            // v2(v1)
            vector(const vector<T>& v)
                :_start(nullptr)
                    , _finish(nullptr)
                    , _end_of_storage(nullptr)
                {
                    vector<T> tmp(v.begin(), v.end());
                    swap(tmp);
                }

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

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

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

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

                return _start[pos];
            }

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

                return _start[pos];
            }

            size_t size() const
            {
                return _finish - _start;
            }
            //相关函数
            void reserve(size_t n)
            {
                if (n > capacity())
                {
                    size_t sz = size();
                    T* tmp = new T[n];
                    if (_start)
                    {
                        //memcpy(tmp, _start, sizeof(T)*sz);
                        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, const T& val = T())
            {
                if (n > capacity())
                {
                    reserve(n);
                }

                if (n > size())
                {
                    // 初始化填值
                    while (_finish < _start + n)
                    {
                        *_finish = val;
                        ++_finish;
                    }
                }
                else
                {
                    _finish = _start + n;
                }
            }

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

                *_finish = x;
                ++_finish;*/
                insert(end(), x);
            }

            void pop_back()
            {
                assert(_finish > _start);
                --_finish;
            }

            iterator insert(iterator pos, const T& x)
            {
                assert(pos >= _start);
                assert(pos <= _finish);

                if (_finish == _end_of_storage)
                {
                    size_t len = pos - _start;
                    reserve(capacity() == 0 ? 4 : capacity() * 2);
                    pos = _start + len;
                }

                // 挪动数据
                iterator end = _finish - 1;
                while (end >= pos)
                {
                    *(end + 1) = *end;
                    --end;
                }
                *pos = x;

                ++_finish;

                return pos;
            }

            // stl 规定erase返回删除位置下一个位置迭代器
            iterator erase(iterator pos)
            {
                assert(pos >= _start);
                assert(pos < _finish);

                iterator begin = pos + 1;
                while (begin < _finish)
                {
                    *(begin - 1) = *begin;
                    ++begin;
                }

                --_finish;
                //if (size() < capacity()/2)
                //{
                //	// 缩容 -- 以时间换空间
                //}

                return pos;
            }

            T& front()
            {
                assert(size() > 0);

                return *_start;
            }

            T& back()
            {
                assert(size() > 0);

                return *(_finish - 1);
            }

            private:
            iterator _start;
            iterator _finish;
            iterator _end_of_storage;
        };
}

后记

这篇我们主要讲了vector是怎么实现的，首先搭建大概的框架，然后实现构造函数，再拓展到构造的其他方式，有拷贝构造、迭代器构造、初始化为N个val的构造等等，它们还有传统和现代两种实现方式，功能都是一样的，只不过思想不一样，现代的实现更加侧重复用和老板思维最后我们实现了相关常见的函数，至此vector便已模拟实现。

对学习这里的同学的建议是，考虑清楚每一个函数的实现目的，再考虑实现方式，以及自己动手撸一遍肯定比只看印象深刻。

感谢大家支持！！！

respect！

下篇见！

在这里插入图片描述