【C++初阶】第十站：vector 中通用函数的模拟实现

vector中的三个重要迭代器

默认成员函数

构造函数(无参构造)

构造函数(函数模板)

情况三：vs2019进行强制检查，erase以后认为it失效了，不能访问，访问就报错

访问容器相关函数

operator[ ]

const operator[ ]

前言：

🎯个人博客：Dream_Chaser

🎈博客专栏：C++

📚本篇内容：vector类通用函数的模拟实现

vector中的三个重要迭代器

在vector当中有三个成员变量_start、_finish、_endofstorage。

_start指向容器的头，_finish指向容器当中有效数据的尾，_endofstorage指向整个容器的尾。

默认成员函数

构造函数(无参构造)

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

我们可以在函数声明处给上缺省值，那么就不用在初始化列表中再初始化了：

class vector
{
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _endofstorage = nullptr;
};

构造函数(函数模板)

这是一个vector构造函数模板，它接收两个迭代器first和last作为参数，用来创建一个新vector，并拷贝first到last范围内的所有元素到这个新vector里。具体操作是遍历这个区间，逐个将元素添加到vector末尾。

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

构造函数(带有默认参数)

size_t

定义了一个向量vector的构造函数，它接受两个参数：元素数量n和一个可选的默认值val。函数首先预留足够的容量来存储n个元素，然后通过一个循环，将val这个值添加到向量中 n次。

如果未提供val，则默认添加该类型默认值，如整数类型的0。这样实现了快速构造一个特定大小且元素具有相同值或默认值的向量对象。

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

int

唯一不同在于第一个函数接受size_t n作为参数，而第二个函数接受int n，这种差异主要体现在参数类型的差别上，建议使用size_t更符合C++标准库容器的惯例，因为它是一种无符号类型，更适合表示容器的大小，能避免负数引发的错误。

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

拷贝构造函数

定义了一个C++向量(vector)类的拷贝构造函数，其功能是创建一个新的vector对象作为现有vector对象的完整副本。

       为新vector预分配与被拷贝vector相同的能力的内存空间，以优化存储管理。

       随后，通过遍历被拷贝vector的所有元素，并逐个将这些元素通过拷贝构造的方式添加到新vector中，实现了元素的深复制，确保了两个vector之间数据的独立性。

        简而言之，这是一个实现深度拷贝的拷贝构造函数，用于高效地创建vector对象的独立复制品。

// 定义一个拷贝构造函数，接受一个const引用类型的vector<T>参数v
vector(const vector<T>& v)
{
    // 首先，为新创建的vector预分配足够的内存来容纳v中的所有元素
    // 通过调用reserve函数设置容量至少为v.capacity()
    reserve(v.capacity());

    // 然后，遍历v中的每一个元素
    for(auto& e : v)
    {
        // 对于v中的每一个元素e，使用push_back成员函数将其添加到当前vector对象中
        // 这里会自动调用T类型的拷贝构造函数来复制元素e
        push_back(e);
    }
}

赋值重载

此 swap 函数通过C++标准库的 std::swap 高效地交换两个 vector 实例的内部指针，实现资源的快速互换。

void swap(vector<T>& v)
{
    std::swap(_start, v._start); // 交换起始指针
    std::swap(_finish, v._finish); // 交换结束指针
    std::swap(_endofstorage, v._endofstorage); // 交换容量指针
}

简单来说就是重写了=操作符的行为，让它可以用于自定义类型（在这里是vector<T>）。这个函数首先创建了一个临时的vector<T>对象tmp，通过拷贝构造初始化为右边要赋值过来的vector<T>。

然后，它使用swap成员函数迅速将当前vector<T>的资源（包括内存指针等）与临时对象tmp交换，这一步骤隐含了原vector<T>资源的清理。最后，函数返回当前对象的引用，以便支持连续赋值（如a = b = c;）。这种方法提高了效率并确保了正确管理内存。

vector<T>& operator=(vector<T> tmp)
{
    swap(tmp); // 使用swap成员函数交换临时对象tmp与当前对象的状态
    return *this; // 返回当前对象的引用，支持链式赋值
}

析构函数

核心任务是清理并释放由vector实例所占用的资源。具体而言，它首先通过delete[] _start;释放了存储元素的数组内存，防止内存泄漏。

将与该vector实例相关的三个关键指针——_start、_finish和_endofstorage——全部赋予nullptr值，不仅提高了程序的安全性，避免了悬挂指针的潜在风险，还便于开发人员在调试过程中识别出这些资源已被妥善清理，且对象处于待销毁的最终状态。

// 定义vector类的析构函数
~vector()
{
    // 释放_start指针指向的动态分配内存，这里是存储vector元素的数组
    delete[] _start;

    // 将_start、_finish和_endofstorage指针全部置为nullptr
    // 目的是：
    // 1. 避免野指针，提高程序运行时的安全性
    // 2. 方便调试， nullptr表明这些资源已被释放
    // 3. 有助于指示该vector对象已完全清理，准备安全销毁
    _start = _finish = _endofstorage = nullptr;
}

迭代器相关函数

vector当中的迭代器实际上就是容器当中所存储数据类型的指针。

// 定义一个迭代器类型，其中T代表某种数据类型，iterator是一个指向该类型T的指针。
typedef T* iterator;

// 定义一个常量迭代器类型，它是一个指向常量的指针，用于遍历不可修改的数据。
// 这意味着通过const_iterator访问的数据不能被修改，保证了数据的安全性。
typedef const T* const_iterator;

begin和end

定义begin()函数，返回指向容器起始元素的迭代器

定义end()函数，返回指向容器最后一个元素之后位置的迭代器

iterator begin()
{
    return _start; // 返回_start指针，它是容器的第一个元素的地址
}

iterator end()
{
    return _finish; // 返回_finish指针，它是容器结束位置的下一位置
}

定义const版本的begin()函数和end()函数，用于不可修改的迭代访问(只读不可写)

const_iterator begin() const
{
    return _start; // 返回指向容器起始的常量迭代器，保证元素不可被修改
}

const_iterator end() const
{
    return _finish; // 返回指向容器结束位置之后的常量迭代器，
                    // 保证迭代访问过程中元素不可被修改
}

容量和大小相关函数

size

返回vector中元素的个数, 这是vector中保存的实际对象的数量，不一定等于它的存储容量。

size_t size()
{
	return _finish - _start;
}

capacity

返回当前为vector分配的存储空间大小，以元素表示

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

resize

n<size，容器的内容会被缩减至前n个元素，移除超出的部分（并销毁这些元素）。

size<n<capacity，容器的内容会通过在末尾插入足够多的元素来扩展，以达到n的大小。如果指定了val值，新插入的元素将初始化为val的副本；如果没有指定val，默认情况下，它们将被赋予默认值初始化(空值)。

n>capacity，那么会自动重新分配已分配的存储空间。

// 该函数用于重新调整容器的大小，并可选地用指定值填充新增的元素
void resize(size_t n, const T& val = T())
{
    // 如果请求的新大小小于等于当前容器的大小，则只需调整_finish指针即可，无需增删元素
    if (n <= size())
    {
        _finish = _start + n; // 将_finish指针前移，使容器表现为缩小
    }
    else
    {
        // 如果请求的新大小大于当前容器的容量，首先确保容量足够大
        reserve(n); // 调整容器的容量至少为n
        
        // 然后，使用指定的值val填充从当前位置到新大小之间的所有元素
        while (_finish < _start + n) // 循环直到到达新的结束位置
        {
            *_finish = val; // 将val赋值给当前位置的元素
            ++_finish; // 移动到下一个位置
        }
    }
}

修改容器内容相关函数

reserve

规则：

要求vector容器容量至少足以容纳n个元素。

如果n大于当前的vector容量，则该函数使容器重新分配其存储空间，将其容量增加到n(或更大)。

在所有其他情况下，函数调用不会导致重新分配，vector容量也不会受到影响。

这个函数对vector的大小没有影响，也不能改变vector的元素:

不影响元素数量
不改变元素内容

拷贝的部分为什么不能使用memcpy：

vector容器存储的是 string 对象，每个 string 对象内部管理着一块动态分配的字符数组。如果直接使用 memcpy 来复制 string 对象，只是浅拷贝了指针和一些成员变量，源对象和复制后的对象会共享同一块字符数组。当源 vector 销毁时，这块字符数组会被释放，导致新 vector 中的字符串变为悬挂指针，访问时会引发未定义行为。

那为什么要用这个编译器默认的赋值重载？

这里强调一个事情就是说：

对于内置类型，由于其直接存储值的特性，复制总是“深拷贝”(直接存储其值，没有指针或间接管理的资源)。而对于自定义类型，尤其是包含动态分配资源的类型，需要明确区分深拷贝和浅拷贝，并根据需要实现深拷贝以保证数据的独立性和正确性。

// 该函数用于重新分配容器的内存，确保至少能容纳n个元素而不必重新分配
void reserve(size_t n)
{
    // 检查请求的容量是否大于当前容量
    if (n > capacity())
    {
        // 分配一个新的内存块，大小为n个T类型的元素
        T* tmp = new T[n];

        // 记录当前容器中元素的数量
        size_t sz = size();

        // 如果原容器已有数据
        if (_start)
        {
            // 将原容器的数据复制到新分配的内存中
            for (size_t i = 0; i < sz; i++)
            {
                tmp[i] = _start[i];
            }

            // 释放原容器占用的内存
            delete[] _start;
        }
        // 更新指针，
        //使得_start指向新内存的开始，
        //_finish指向已有的元素末尾，
        //_endofstorage指向新内存的末尾
        _start = tmp;
        _finish = _start + sz;
        _endofstorage = _start + n;
    }
}

push_back

在vector当前最后一个元素的末尾添加一个新元素。val的内容被复制(或移动)到新元素中。

void push_back(const T& x)
{
  //方法一
  /*if (_finish == _endofstorage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	*_finish = x;
	++_finish;*/
			
   //直接复用:
     insert(end(),x);
}

insert

当 _finish == _endofstorage 说明该容器需要扩容，在此过程中会引发一些bug。

调试过后，发现pos指向的内容变为随机值：

从上述示例中，引出我们迭代器失效的例子：

情况一：pos迭代器失效

扩容后pos失效了，失效原因:扩容导致，原来的迭代器还指向旧的空间

解决办法：更新pos

// 在指定迭代器位置pos前插入一个值为x的元素
void insert(iterator pos, const T& x)
{
    // 断言检查，确保pos位于_start和_finish之间
    assert(pos >= _start);
    assert(pos <= _finish);

    // 如果 Finish 指针已达到存储空间末端，进行扩容
    if (_finish == _endofstorage)
    {
        // 计算当前位置距离_start的距离，用于扩容后重新定位pos
        size_t len = pos - _start;
        // 扩容逻辑：初始为空时至少分配4个单位空间，否则加倍当前容量
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        // 扩容后，根据之前计算的偏移量重新定位pos
        pos = _start + len;
    }

    // 从_finish指针所指位置开始（容器尾部），向后移动所有元素，为新元素腾出空间
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end; // 每个元素向后移动一位
        --end;
    }

    // 在腾出的位置插入新元素x
    *pos = x;

    // 更新_finish指针，表示容器元素数量增加
    ++_finish;
}

情况二: insert之后迭代器失效

怎么避免呢：

erase

情况三：vs2019进行强制检查，erase以后认为it失效了，不能访问，访问就报错

验证erase迭代器失效：

用示例 1 2 3 4 5 验证的时候，发现没有出现问题，但是用 1 2 3 4 5 6 验证则会出现错误：

而且发现用这个验证的时候，2 2 3 4 5，并没有把所有的偶数都删去。

验证 1 2 3 4 5 和 2 2 3 4 5：

当验证 1 2 3 4 5 6时：

当循环中删除元素后直接使用++it，如果该元素正好是最后一个满足删除条件的元素，那么在删除后，it会指向容器的end()，此时再执行++it就会越界，尤其是在开启了迭代器调试检查的编译器环境下（如VS2019的迭代器检查功能），会直接报告错误。

不能直接++it，如果没有删除元素，才进行迭代器的自增

	void test_vector5()
	{
		//1  2   3   4   5  
		//1  2   3  4    5  6
		//2  2   3   4   5
		std::vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		auto it = v.begin();
		while (it != v.end())
		{
			//vs2019进行强制检查，erase以后任务it失效了，不能访问，访问就报错
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
			{
				++it;
			}
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

访问容器相关函数

operator[ ]

非 const版本的 operator[ ] 允许对容器内的元素进行读写操作。

这个函数被调用时，它会直接返回 _start[pos] ，即容器起始地址偏移pos位置的元素的引用。由于返回的是引用，所以可以通过这个返回值来修改容器内的元素。

// 非const版本的下标访问运算符
T& operator[](size_t pos)
{
    // 断言检查传入的索引pos是否小于当前容器的大小，确保索引合法
    assert(pos < size());

    // 返回指定位置pos的元素的引用，允许用户修改该元素
    return _start[pos];
}

const operator[ ]

const 版本的 operator[ ] 主要用于 const对象或者通过 const引用访问容器时。它返回元素的常量引用，意味着通过这种方式访问到的元素是只读的，不能被修改，从而保证了容器在声明为const时的数据完整性。

// const版本的下标访问运算符
const T& operator[](size_t pos) const
{
    // 同样进行索引合法性检查
    assert(pos < size());

    // 返回指定位置pos的元素的常量引用，保证该元素不可被修改
    return _start[pos];
}