【爱上C++】vector模拟实现

  • 开发
  • 22

文章目录

前言

上一节我们讲了vector的基本使用，现在我们讲解vector的模拟实现，其中有三大重难点：
1.vector是如何进行设计与封装的
2.迭代器失效问题
3.memcpy,memmove导致的浅拷贝问题

一：基本框架

1.结构的定义

#include <iostream>
#include <assert.h>
using namespace std;
namespace myvector
{
	template<class T>
	class vector {
	public:
		// Vector的迭代器是一个原生指针
		typedef T* iterator;
		typedef const T* const_iterator;


	private:
		iterator _start;        // 开始位置
		iterator _finish;		// 结束位置
		iterator _endofstorage;	// end of storage
	};
}

在 vector 类中，我们通常会使用_指针_来表示迭代器，因为指针天然支持指针算术运算和解引用操作，可以方便地遍历和访问元素。使用 typedef 定义迭代器类型可以使代码更加灵活和可维护。

使用 iterator 类型有以下几个原因：

  1. 可读性和维护性： 使用 iterator 使得代码更具可读性。例如，当看到 iterator 类型时，很容易理解这是一个指向容器元素的指针，而不是其他类型的指针。
  2. 灵活性： 如果将来需要更改迭代器的实现方式，只需要修改 typedef 定义，而不需要修改所有使用迭代器的代码。例如，如果将来决定使用自定义的迭代器类，而不是原始指针，只需要修改 typedef 语句。
  3. 与 STL 接口一致： 这使得 vector 类的接口与标准模板库（STL）容器的接口一致，便于用户使用和理解。例如，STL 容器如 std::vector 也使用迭代器来遍历和操作元素。

_start：

  • 这是一个指针，指向分配的内存空间中的第一个元素。
  • 在 vector 类中，_start 指向当前存储的第一个元素的位置。

_finish：

  • 这是一个指针，指向当前存储的最后一个元素之后的位置。
  • 在 vector 类中，_finish 指向最后一个元素的下一个位置。即，有效元素的范围是从 _start 到 _finish-1。

_endofstorage：

  • 这是一个指针，指向分配的内存空间的末尾位置。
  • 在 vector 类中，_endofstorage 指向当前分配的内存空间的末尾，即容器可以存储元素的最大位置。

image.png
所以由图我们可以知道：
_size=_finish-_start
_capacity=_endofstorage-_start

2.构造函数

构造函数有三类：无参构造函数，带参构造，迭代器区间构造放在 二：迭代器的实现 中讲述。

//无参默认构造
vector() 
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{

}

// 带参构造函数，创建包含 n 个 val 值的 vector
vector(size_t n, const T& val = T())
{
    resize(n, val);
}
//带参构造（int）
vector(int n, const T& val = T())
{
    resize(n, val);
}

①.详解 const T& val = T()

关于 const T& value = T() 作为默认参数的详细解释，我们需要理解以下几个概念：默认参数、匿名对象、以及如何结合使用它们。
默认参数
默认参数允许函数在调用时省略某些参数。编译器会使用提供的默认值来填补这些被省略的参数。对于构造函数来说，默认参数提供了一种灵活的初始化方式。
匿名对象
匿名对象是指没有绑定到任何变量的临时对象。在 C++ 中，可以通过直接调用构造函数来创建匿名对象。例如，T() 就是一个创建类型为 T 的默认构造对象的表达式。
const T& value = T()
现在，让我们将这些概念结合起来看 const T& value = T() 是如何工作的。

  1. 默认参数的使用
    在构造函数定义中：
    vector(int n, const T& value = T())
    value 是一个默认参数，其默认值是一个匿名对象 T()。
  2. 匿名对象的创建
    T() 表达式创建了一个类型为 T 的匿名对象。对于基础类型 int，T() 等价于 0。对于用户定义的类型 T，它调用 T 的默认构造函数创建一个默认初始化的对象。
  3. 引用绑定
    const T& value = T() 意味着默认参数 value 是一个对匿名对象的常量引用。这里引用了临时对象，但因为是常量引用，所以该临时对象在整个函数调用过程中是有效的（临时对象的生命周期延长至引用的生命周期结束）。

②.为什么要多加一个int类的带参构造？】

思考一下，如果不加vector(int n, const T& val = T())，下面这个代码是否有问题？

vector<string> v1(5, "1111");
for (auto e : v1)
    {
        cout << e << " ";
    }
cout << endl;
vector<int> v2(5, 1);
for (auto e : v2)
    {
        cout << e << " ";
    }
cout << endl;

上面这个代码看似没问题，如果没有vector(int n, const T& val = T())就会报错
image.png
原因如下图:
image.png
v2优先匹配上迭代器构造，此时会造成 非法间接寻址 错误

再举另外一个例子
vector<int> v(10, 5);
编译器在编译时，认为T已经被实例化为int，而10和5编译器会默认其为int类型
就不会走vector(size_t n, const T& value = T())这个构造方法，最终选择的是：vector(InputIterator first, InputIterator last)。
因为编译器觉得区间构造两个参数类型一致，因此编译器就会将InputIterator实例化为int，但是10和5根本不是一个区间，编译时就报错了，故需要增加该构造方法

3.析构函数

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

4.size()和capacity()

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

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

根据上面的图，很容易的理解size()和capacity()

5.push_back尾插

void push_back(const T& x)
{
    if (_finish == _endofstorage)//如果满了则要扩容
    {
        size_t  newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        //如果 capacity() == 0,则让 capacity()=4，
        //如果 capacity() !=0 ,则让 capacity()=capacity()*2
        reserve(newcapacity);
    }
    *_finish = x;
    ++_finish;
}
void pop_back()
{
    assert(size()>0);
    --_finish;
}

6.operator[]


//返回 T& 是因为 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];
}

operator[]的返回类型为T&有以下几个原因：

  1. 方便读写操作：
    • 返回T&（T的引用）可以同时支持读和写操作。如果返回的是值（T），你只能读取值，不能修改。
vector<int> v(10, 0);
v[0] = 5; // 可以通过 T& 引用修改值
int x = v[1]; // 读取值
  1. 避免不必要的拷贝：
    • 返回引用避免了拷贝，提升了性能。如果返回值（T），每次访问元素时都会进行拷贝，这在处理大对象时会显著影响性能。
    • 例如，返回引用只需要获取对象的地址，而不需要实际拷贝对象的数据。
  2. 一致性和习惯用法：
    • 标准库中的std::vector和其他容器都采用这种设计。遵循这种设计可以确保自定义容器的接口和行为与标准容器一致，减少学习和使用上的障碍。

二：迭代器的实现

1.begin()和end()

image.png

  		//普通对象的迭代器：提供对容器元素的读写访问。
		//begin
		iterator begin()
		{
			return _start;
		}
		//end
		iterator end()
		{
			return _finish;
		}

		//常量对象的迭代器：提供对容器元素的只读访问。
		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

测试一下

    void test_vector10()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			it++; //注意不要写成*it++
		}
		cout << endl;
	}

image.png

2.迭代器区间构造

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

详细讲解：

  1. 模板参数 InputIterator:
    InputIterator 是一个模板参数，表示输入迭代器的类型。可以是指针、标准库迭代器（如std::vector::iterator）或者用户定义的迭代器。
    通过使用模板，这个构造函数可以处理各种类型的迭代器，从而支持不同的容器和数据结构。
  2. 参数 first 和 last:
    first 和 last 是两个迭代器，表示要复制的元素区间的起始和结束位置。
    这个区间是半开区间 [first, last)，即包含 first 指向的元素，但不包含 last 指向的元素。
  3. 构造函数主体:
    构造函数通过遍历 [first, last) 区间，将每个元素插入到当前vector对象中。
  4. 操作步骤:
    初始化:
    InputIterator first, last 定义了两个迭代器，分别指向待复制元素的起始位置和结束位置。
    循环:
    while (first != last) 循环遍历从 first 到 last 的区间。
    在每次循环中，通过 *first 解引用 first 指向的元素，并使用 push_back(*first) 将其添加到vector对象的末尾。
    使用 ++first 将 first 移动到下一个元素。

举个例子应用一下：

	void test_vector10()
	{
		int arr[5] = { 2,3,4,5,6 };
		vector<int>v1(arr, arr + 5);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}

运行结果如下：
image.png
此时的first就是arr,last就是arr+5

三：reserve 引发的相关问题

1.内部迭代器失效

在动态数组的 reserve 函数中，如果新预留的空间 n 大于当前的容量 capacity()，则需要进行扩容操作。代码如下：

void reserve(size_t n)
{
    if (n > capacity())
    {
        //1.申请新空间
        T* tmp = new T[n];
        //2.将原有数据拷贝到新空间当中
        memmove(tmp, _start, sizeof(T) * size());
        //3.释放原有空间
        delete _start;
        //4.指向新空间
        _start = tmp;
        _finish = _start + size();
        _endOfStorage = _start + capacity();
    }
}

乍一看，这段代码似乎是正确的，然而实际上存在一个严重的问题：野指针问题。在扩容之后，_finish 和 _endOfStorage 仍然指向旧空间的对应位置。
问题分析:
我们来详细分析这段代码的执行过程：

  1. 申请新空间：T* tmp = new T[n];
  2. 拷贝数据：memmove(tmp, _start, sizeof(T) * size());
  3. 释放旧空间：delete _start;
  4. 更新指针：_start = tmp; 然后 _finish 和 _endOfStorage 指向新空间的位置。

问题出在第四步，虽然 _start 更新到了新空间，但 _finish 和 _endOfStorage 指向的是新空间中的不正确位置，因为它们是基于旧空间的 size 和 capacity 计算的。
image.png
解决方法:
我们需要在释放旧空间之前保存旧空间的 size，并在新空间中重新计算 _finish 和 _endOfStorage。
正确的实现:
下面是修改后的 reserve 函数，解决了野指针问题：

void reserve(size_t n)
{
    if (n > capacity())
    {
        //1.保存原有空间的size
        size_t oldSize = size();
        //2.开辟新空间
        T* tmp = new T[n];
        //3.将原有空间的数据拷贝到新空间当中
        memmove(tmp, _start, sizeof(T) * oldSize);
        //4.释放旧空间
        delete[] _start;
        //5.指向新空间
        _start = tmp;
        _finish = _start + oldSize;
        _endOfStorage = _start + n;
    }
}

详细步骤：

  1. 保存原有空间的 size：size_t oldSize = size();
  2. 开辟新空间：T* tmp = new T[n];
  3. 拷贝数据到新空间：memmove(tmp, _start, sizeof(T) * oldSize);
  4. 释放旧空间：delete[] _start;
  5. 更新指针指向新空间：_start = tmp;，_finish = _start + oldSize;，_endOfStorage = _start + n;

2.外部迭代器失效

void reserve(size_t n)
{
    if (n > capacity())
    {
        //1.保存原有空间的size
        size_t oldSize = size();
        //2.开辟新空间
        T* tmp = new T[n];
        //3.将原有空间的数据拷贝到新空间当中
        memmove(tmp, _start, sizeof(T) * oldSize);
        //4.释放旧空间
        delete[] _start;
        //5.指向新空间
        _start = tmp;
        _finish = _start + oldSize;
        _endOfStorage = _start + n;
    }
}

这段代码在处理内置类型（如 int）时没有问题，但当处理自定义类型（如 std::string）时会导致浅拷贝问题，进而引发内存管理错误。
问题分析：
浅拷贝问题：
浅拷贝是指直接拷贝对象的内存内容，而不考虑对象中的指针和动态分配的内存。这在处理内置类型时通常是安全的，但对于包含指针或动态内存的自定义类型，会导致多个对象指向同一块内存，从而引发多次释放同一内存的问题。
例如，当 vector 存储 std::string 类型时：

void test_vector10()
{
    vector<string> v1;
    v1.push_back("abc");
    v1.push_back("def");
    v1.push_back("exd");
    for (auto& e : v1)
    {
        cout << e << " ";
    }
    cout << endl;
}

在 reserve 扩容后，浅拷贝会导致同一块内存被多个 string 对象引用，最终导致程序崩溃和断言错误。
解释如图（放大观看）：
image.png
解决方法
我们需要避免浅拷贝，确保在扩容时进行深拷贝。对于自定义类型，使用赋值运算符重载来实现深拷贝是关键。

3.正确的实现

下面是修改后的 reserve 函数，解决了浅拷贝问题：

void reserve(size_t n)
{
    if (n > capacity())
    {
        // 提前保存偏移量oldSize
        size_t oldSize = size();
        // 1.申请新空间
        T* tmp = new T[n];
        // 2.将原有空间中的数据拷贝到新空间当中
        for (size_t i = 0; i < oldSize; i++)
        {
            tmp[i] = _start[i];  
            // 内置类型直接赋值，自定义类型调用赋值运算符重载，进行深拷贝
        }
        // 3.释放原有空间
        delete[] _start;
        // 4.将_start, _finish, _endOfStorage都指向到新空间
        _start = tmp;
        _finish = _start + oldSize;
        _endOfStorage = _start + n;
    }
}

详细步骤

  1. **保存原有空间的 **size：size_t oldSize = size();
  2. 开辟新空间：T* tmp = new T[n];
  3. 拷贝数据到新空间：使用赋值运算符进行深拷贝：
for (size_t i = 0; i < oldSize; i++)
{
    tmp[i] = _start[i];
}
  1. 释放旧空间：delete[] _start;
  2. 更新指针指向新空间：_start = tmp;，_finish = _start + oldSize;，_endOfStorage = _start + n;

_start 指针的作用

_start 是指向动态数组首元素的指针。我们可以通过下标运算符（[]）来访问动态数组中的元素。例如，_start[i] 表示数组中的第 i 个元素。指针和数组在 C++ 中有很多相似之处，特别是在内存访问上。

_start[i] 的含义

当我们使用 _start[i] 时，相当于对指针进行偏移访问。这是因为 T* _start 是指向类型 T 的指针，_start[i] 等价于 *(_start + i)，即访问 T 类型数组的第 i 个元素。

4.memcpy带来的问题

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

int main()
{
myvector::vector<myvector::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}

问题分析：

  1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
  2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且
    自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

image.pngimage.pngimage.pngimage.png
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

四：insert 引发的相关问题

先看看insert的代码

		void insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish); // 确保插入位置合法
			if (_finish == _endofstorage) // 如果存储空间已满
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩充存储空间
			}
			iterator end = _finish - 1; // 初始化end为最后一个元素的位置
			while (end >= pos) // 从后向前移动元素，直到插入位置
			{
				*(end + 1) = *end; // 将元素向后移动一位
				end--; // 继续向前移动
			}
			*pos = x; // 在插入位置插入新元素
			++_finish; // 更新_finish指针
		}

我们来测试一下：
image.png
结果如下：
image.png
为什么呢?

1.内部迭代器失效

内部迭代器失效指的是，当容器进行某些操作（例如内存重新分配）时，容器内部的迭代器（即正在被容器使用或操作的迭代器）由于这些操作而失效。在你的代码中，pos 作为插入操作中的一个内部迭代器，在调用 reserve 扩充存储空间时，可能会因为内存重新分配而失效。这种失效主要发生在容器的实现内部，开发者需要在实现容器操作时特别注意。

迭代器失效问题：

  • 当 _finish == _endofstorage 时，调用 reserve 可能会重新分配内存并复制现有元素到新的存储位置。此时，所有指向旧存储位置的迭代器（包括 pos 和 end）都会失效。

解决办法
在调用 reserve 之后，重新计算 pos 和 end 的位置，确保插入操作在新的存储位置上进行。使用更通用和安全的方法来处理迭代器操作。

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

			// 检查是否需要增容
			if (_finish == _endofstorage) {
				// 扩容会导致迭代器失效，扩容需要更新一下 pos
				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++;
		}

我们运行一下看看
image.png
这样就没问题啦！
但是！这段代码其实还是存在问题的

2.外部迭代器失效

外部迭代器失效指的是，容器外部的代码在使用容器的迭代器时，由于容器内部发生了某些操作（如内存重新分配、元素删除等），导致这些外部使用的迭代器变得无效。这通常发生在用户代码中，当用户在迭代容器并同时对容器进行修改时，外部的迭代器会失效。

看看下面这个测试函数能不能通过？

	void test_vector10()
	{
		vector<int> v;
		v.push_back(10);
		v.push_back(20);
		v.push_back(30);
		v.push_back(40);
		vector<int>::iterator it = v.begin();
		v.insert(it, 99); // 插入 99
		v.insert(it + 1, 111); // 再插入 111
		for (auto e = v.begin(); e != v.end(); ++e) {
			cout << *e << " ";
		}
		cout << endl;
	}

调试一下
image.png
image.png
image.png
详细解释

  1. 向量扩容前的情况：
    • 初始容量为0，第一次调用 push_back 时会将容量扩展为4。
    • 插入10、20、30、40后，向量状态如下：
容量: 4
内容: [10, 20, 30, 40]
  1. 插入新元素99：
    • 调用 v.insert(it, 99) 时，it 是 v.begin()，即指向10的位置。
    • insert 过程中，如果容量不够，会调用 reserve 增加容量（假设容量增加到8）。
    • 扩容后，it 仍然指向新分配内存中的位置，但是**外部的 ****it** 迭代器并没有被更新，它仍然指向旧的内存位置，这就导致了 it 成为野指针。
    • 插入操作成功后，向量状态如下：
容量: 8
内容: [99, 10, 20, 30, 40]
  1. 再次插入新元素111：
    • 调用 v.insert(it + 1, 111) 时，it + 1 是一个野指针，指向旧内存位置，这会导致未定义行为，程序可能崩溃或插入失败。

解决问题
返回有效迭代器
在 insert 方法中返回插入位置的新迭代器，并在调用代码中使用返回的迭代器进行后续操作。

/* 插入 */
iterator insert(iterator pos, const T& x) {
	assert(pos >= _start);
	assert(pos <= _finish);
 
	// 检查是否需要增容
	if (_finish == _endofstorage) {
		// 扩容会导致迭代器失效，扩容需要更新一下 pos
		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;
}

调用代码使用返回的迭代器
image.png

总结
通过在 insert 方法中返回有效的迭代器，并在调用代码中使用返回的迭代器，可以有效避免迭代器失效问题。这种方法确保即使容器内部进行了扩容操作，外部代码仍然可以使用有效的迭代器进行后续操作，从而避免未定义行为和潜在错误。

五：erase 引发的相关问题

erase 代码：

		void erase(iterator pos)
		{
			assert(pos <= _finish);
			assert(pos >= _start);
			iterator begin = pos + 1;
			while (begin < _finish)
			{
				*(begin - 1) = *begin;
				begin++;
			}
			_finish--;
		}

问题分析
在原始的 erase 函数中，当我们删除一个元素时，容器会重新排列后续的元素以填补被删除元素的位置。这种操作会使得原本指向删除位置的迭代器 pos 失效。失效的迭代器在后续操作中继续使用，可能会导致程序出现未预期的行为。
具体来说，在下面的测试函数 test_vector8 中：

void test_vector10()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(4);
    v.push_back(5);
    vector<int>::iterator it = v.begin();
    //删除所有偶数
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            v.erase(it);
        }
        ++it;
    }
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

删除偶数的过程中，存在以下几种情况：

  1. 数据 [1, 2, 3, 4, 5]：程序运行正常，但这只是一个巧合，因为被删除的元素后面恰巧是一个非偶数。
  2. 数据 [1, 2, 3, 4]：程序崩溃。删除最后一个偶数后，迭代器 pos 已经失效，再次 pos++ 可能导致迭代器越界。
  3. 数据 [1, 2, 4, 5]：程序结果不正确。删除一个偶数后，迭代器 pos 指向了下一个元素，此时由于连续的偶数，第二个偶数没有被判断和删除。

分析具体情况

  • 数据 [1, 2, 3, 4, 5]：在第一次删除 2 后，容器重新排列，3 移到原本 2 的位置，迭代器 pos 失效，但因为 pos++ 后指向了 3（新位置），后续操作没有影响，这种情况是巧合。
  • 数据 [1, 2, 3, 4]：删除 2 后，3 移到原来 2 的位置，再次 pos++ 指向了 4。删除 4 后，迭代器指向了 _finish，再 pos++ 会越过容器的边界，导致程序崩溃。
  • 数据 [1, 2, 4, 5]：删除 2 后，4 移到原来 2 的位置，再次 pos++ 指向了 5，跳过了 4，导致 4 未被删除。

根本原因

  1. 迭代器失效：erase(pos) 操作后，pos 不再指向有效的位置。容器内存重新排列后，pos 的位置已经失效，继续使用失效的迭代器会导致未定义行为。
  2. 迭代器的无效递增：在删除元素后，pos 应该被更新为指向下一个有效的位置，而不是简单地递增 pos++。直接递增失效的迭代器会导致逻辑错误和潜在的崩溃。
  3. 容器的内存管理：一些 vector 实现可能会在 erase 操作中进行内存的重新分配（虽然大多数实现不会），这会导致所有迭代器失效，操作失效的迭代器会引发更严重的问题。

通过修改 erase 函数使其返回删除操作后下一个有效的迭代器，并在删除操作后更新迭代器来解决这些问题，可以确保程序正确运行。

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

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

    _finish--;
    return pos;
}

通过这种方式，我们可以确保在删除元素后，迭代器始终指向下一个有效的位置，从而避免迭代器失效导致的未定义行为和程序崩溃。

iterator erase(iterator pos)
{
    assert(pos <= _finish);
    assert(pos >= _start);
    iterator begin = pos + 1;
    while (begin < _finish)
    {
        *(begin - 1) = *begin;
        begin++;
    }
    _finish--;
    return pos;
}
void test_vector10()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(4);
    v.push_back(5);
    vector<int>::iterator it = v.begin();
    // 删除所有偶数
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            it = v.erase(it);
        }
        else
        {
            ++it;
        }
    }
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

修改后的执行过程

  1. it 指向 1，不是偶数，it++。
  2. it 指向 2，是偶数，调用 it = v.erase(it)，v 变为 [1, 3, 4, 4, 5]，it 指向 3。
  3. it 指向 3，不是偶数，it++。
  4. it 指向 4，是偶数，调用 it = v.erase(it)，v 变为 [1, 3, 4, 5]，it 指向 4。
  5. it 指向 4，是偶数，调用 it = v.erase(it)，v 变为 [1, 3, 5]，it 指向 5。
  6. it 指向 5，不是偶数，it++，此时 it 到达 v.end()，循环结束。

最终结果为 [1, 3, 5]，正确删除所有偶数，问题解决。

六：其他操作

resize

void resize(size_t n,const T& val= T())
{
//如果没传实参，就是一个半缺省，缺省值就是一个匿名对象，那就看默认构造的是什么
    if(n>size())
    {
        reserve(n);
        while(_finish<_start+n)
        {
             *_finish=val;
             ++_finish;
         }
    }
    else
    {//直接改变_finish  相当于删除
        _finish=_start+n;
    }	

}

为什么缺省参数要这样写？
兼容模板
在模板类中，成员函数需要适应各种类型的参数。默认构造函数 T() 适用于大多数类型，因此能够确保 resize 函数可以正确处理不同类型的对象。例如：
对于基本类型（如 int），T() 将初始化为 0。
对于自定义类型，如果提供了默认构造函数，T() 将调用该构造函数。
对于指针类型，T() 将初始化为 nullptr。
缺省参数的灵活性
缺省参数 val = T() 允许用户在调用 resize 函数时选择性地提供填充值。如果用户没有提供，resize 函数将使用 T() 作为默认值，这样可以简化函数调用，并使代码更具通用性。

赋值运算符重载

传统写法：

        //1.开空间 2.拷贝数据 3。释放原有空间 4.指向新空间
		vector <T>& operator=(const vector<T>& v)
		{
			if (this != &v)
			{
				T* tmp = new T[v.capacity()];
				for (int i = 0, i < v.size(), i++)
				{
					tmp[i] = v._start[i]; 
//_start 是一个指向动态分配数组首元素的指针。这个指针类似于数组的首地址，因此可以通过索引访问数组中的元素，就像使用数组一样
				}
				delete[] _start;
				_start = tmp;
				_finish = _start + v.size();
				_endofstorage = _start + v.capacity();
			}
			return *this;
		}

现代写法

		void swap(const vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstroage, v._endofstroage);
		}
		vector <T>& operator=(const vector<T> v)
		{
			swap(v);
			return *this;
		}

现代写法主要采用了一个名为“拷贝并交换”（copy and swap）的惯用法。这个方法简化了赋值运算符的实现，使代码更易于编写和维护，同时也提高了代码的异常安全性。让我们详细解释一下现代写法的思路以及为什么传参时不能使用引用。

现代写法的思路

步骤解释：

  1. 构造临时对象：在赋值运算符中，传递的是一个值（而不是引用），这会导致在调用时先复制一份参数 v，然后在函数体内操作这个副本。这会自动调用 vector 的拷贝构造函数来创建一个临时对象。
  2. 交换数据：使用 swap 函数交换当前对象和临时对象的内部数据指针。这样做的好处是交换操作只涉及指针交换（通常是常量时间操作），而不会涉及到实际数据的移动或拷贝。
  3. 销毁临时对象：由于临时对象在函数退出时会被销毁，它会自动释放原对象的数据内存。

为什么现代写法传参数时不能传引用？

1. 异常安全性：
现代写法通过值传递来确保异常安全性。在值传递的过程中，会调用拷贝构造函数。如果这个拷贝构造函数抛出异常，赋值操作会被终止，并且不会改变现有对象的状态。这样可以避免资源泄漏或部分更新对象状态的不一致问题。
2. 确保交换的对象是副本：
通过值传递，在进入赋值运算符函数时，会创建一个参数对象的副本。如果我们使用引用传递，我们将直接操作原对象，这可能导致未定义的行为。比如，如果 v 和 this 引用的是同一个对象，swap(v) 将会交换同一个对象的数据，导致不可预测的行为。
3. 简化代码：
这种方法使得赋值运算符实现更加简洁，只需关注如何交换对象的内部数据，而不需要手动管理内存分配和释放。这也减少了代码出错的机会。
示例：
假设我们有如下对象：

vector<int> v1 = {1, 2, 3};
vector<int> v2 = {4, 5, 6};

v1 = v2; // 调用赋值运算符

在赋值运算符内部，会创建一个 v2 的副本，然后 v1 的数据与这个副本进行交换。最终，v1 拥有 v2 的数据，临时副本在交换后被销毁，释放原 v1 的数据。

现代写法传参为什么不能传引用的具体原因：

vector<T>& operator=(const vector<T>& v) {
    vector<T> tmp(v); // 创建v的副本
    swap(tmp); // 交换当前对象与临时副本的数据
    return *this;
}

如果传递的是引用，那么传递的就是原对象。假设在某个操作中发生异常，可能导致原对象 v 状态不一致或资源泄漏。而通过值传递，创建一个临时副本，即使发生异常，临时副本的资源管理和释放都由其自身处理，原对象 v 不会受到影响。
综上所述，现代写法的主要思想是利用“拷贝并交换”技术，通过值传递参数来确保异常安全性、简化代码实现，并避免资源管理的复杂性。

七：完整代码

#pragma once
#include<assert.h>
//底层实现 +做题
//02:22:12    题7. 电话号码字母组合OJ



namespace myvector
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		
		//无参默认构造
		vector() 
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{

		}

		//析构
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstorage = nullptr;
			}

		}


		//拷贝构造-两种写法
		//1.
		//vector(const vector<T>& v)
		//{
		//	_start = new T[v.capacity()];
		//	memcpy(_start, v._start, v.size() * sizeof(T));
		//	_finish = _start + v.size(); 
		//	....
		//}
		//2.
		//v2(v1);
		vector(const vector<T>& v)
		{
			reserve(v.capacity());//先给v2 开和v1同样大的空间
			for (const auto& e : v)//取v里面的值依次赋值给e，加引用深拷贝，更好
			{
				push_back(e);
			}
		}

		//赋值运算符重载
		//传统写法：
		//1.开空间 2.拷贝数据 3。释放原有空间 4.指向新空间
		vector <T>& operator=(const vector<T>& v)
		{
			if (this != &v)
			{
				T* tmp = new T[v.capacity()];
				for (int i = 0, i < v.size(), i++)
				{
					tmp[i] = v._start[i]; 
//_start 是一个指向动态分配数组首元素的指针。这个指针类似于数组的首地址，因此可以通过索引访问数组中的元素，就像使用数组一样
				}
				delete[] _start;
				_start = tmp;
				_finish = _start + v.size();
				_endofstorage = _start + v.capacity();
			}
			return *this;
		}
		//现代写法
		void swap(const vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstroage, v._endofstroage);
		}
		vector <T>& operator=(const vector<T> v)
		{
			swap(v);
			return *this;
		}

		//迭代器区间构造.
//构造函数允许你用任何支持迭代器的区间（例如其他容器中的元素）来初始化一个 vector 对象。
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		带参构造
		vector(size_t n, const T& val = T())
		{
			resize(n, val);
		}
		带参构造（int）
		vector(int n, const T& val = T())
		{
			resize(n, val);
		}

		//赋值-现代写法      
		//v1=v3;
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}
		vector<T>& operator =  (vector<T> v)   //为什么那里不能用引用，仔细想.02:06:13  
		{							//如果用了引用就是 v1和v3交换，而不是v1和v3带来的那个临时变量v 交换
			swap(v);
			return *this;
		}


		//普通对象的迭代器：提供对容器元素的读写访问。
		//begin
		iterator begin()
		{
			return _start;
		}
		//end
		iterator end()
		{
			return _finish;
		}

		//常量对象的迭代器：提供对容器元素的只读访问。
		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

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



		//这里注意还是要判断n>capacity，因为reserve 也可能单独使用，不能搞成缩容了
		//void reserve
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t old = size();//保存当前大小,返回的size()是新的
				T* tmp = new T[n];//分配新的内存
				if (_start)//复制旧数据到新内存
				{
					//memcpy(tmp, _start, old * sizeof(T));  memcpy会出问题，是一种浅拷贝test7(),02:03:28
					for (size_t i = 0; i < old; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
//当你重新分配内存时，_finish 和 _endofstorage 的值会基于 size() 和 capacity() 更新
				//更新指针
				_start = tmp; 
				_finish = _start + old; //将 _finish重新设置为旧大小的位置
				//_finish=_start+size();   错的
				//删除 old 后，_finish 指针将指向新容量的末尾，而不是当前元素的末尾。这意味着 _finish 会指向一个未初始化的位置，导致对向量的操作（如 push_back）出现未定义行为。
				_endofstorage = _start + n; // 将 _endofstorage 设置为新容量的位置
				//_endofstorage=_start+capacity();

			}
		}



		void resize(size_t n, T val = T())

		{//三种情况假设有5个数据，容量为10.则有resize(3),resize(7),resize(14)三种情况
			if (n > size())
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				_finish = _start + n;
			}
		} 
		//为什么缺省参数能这样写？
		//兼容模板
		//	在模板类中，成员函数需要适应各种类型的参数。默认构造函数 T() 适用于大多数类型，因此能够确保 resize 函数可以正确处理不同类型的对象。例如：
		//	对于基本类型（如 int），T() 将初始化为 0。
		//	对于自定义类型，如果提供了默认构造函数，T() 将调用该构造函数。
		//	对于指针类型，T() 将初始化为 nullptr。
		//缺省参数的灵活性
		//	缺省参数 val = T() 允许用户在调用 resize 函数时选择性地提供填充值。如果用户没有提供，resize 函数将使用 T() 作为默认值，这样可以简化函数调用，并使代码更具通用性。
		//  


		void push_back(const T& x)
		{
			if (_finish == _endofstorage)
			{
				size_t  newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				//如果 capacity() == 0,则让 capacity()=4，
				//如果 capacity() !=0 ,则让 capacity()=capacity()*2
				reserve(newcapacity);
			}
			*_finish = x;
			++_finish;
		}

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


		//vector 不支持头插  头删

		//pos位置之前插入x

		//下面这个代码多次运行会失效，原因：迭代器失效。 pos扩容后失效，及时更新即可。
		//
		//void insert(iterator pos, const T& x)
		//{
		//	assert(pos >= _start && pos <= _finish); // 确保插入位置合法
		//	if (_finish == _endofstorage) // 如果存储空间已满
		//	{
		//		reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩充存储空间
		//	}
		//	iterator end = _finish - 1; // 初始化end为最后一个元素的位置
		//	while (end >= pos) // 从后向前移动元素，直到插入位置
		//	{
		//		*(end + 1) = *end; // 将元素向后移动一位
		//		end--; // 继续向前移动
		//	}
		//	*pos = x; // 在插入位置插入新元素
		//	++_finish; // 更新_finish指针
		//}


		/* 插入 */
		//void insert(iterator pos, const T& x) {
		//	assert(pos >= _start);
		//	assert(pos <= _finish);

		//	// 检查是否需要增容
		//	if (_finish == _endofstorage) {
		//		// 扩容会导致迭代器失效，扩容需要更新一下 pos
		//		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++;
		//}


		//解决： 
		/* 插入 */
		iterator insert(iterator pos, const T& x) {
			assert(pos >= _start);
			assert(pos <= _finish);

			// 检查是否需要增容
			if (_finish == _endofstorage) {
				// 扩容会导致迭代器失效，扩容需要更新一下 pos
				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;
		}

			//注意是 从pos起始位置往后的所有数据，挪到pos+1上
			//memmove(pos + 1, pos, sizeof(T) * (_finish - pos));



		//删除pos位置数据
		//void erase(iterator pos)
		//{
		//	assert(pos >= _start && pos < _finish);
		//	memmove(pos, pos + 1, sizeof(T) * (_finish - pos));
		//	--_finish;
		//}

		//void erase(iterator pos)
		//{
		//	assert(pos <= _finish);
		//	assert(pos >= _start);
		//	iterator begin = pos + 1;
		//	while (begin < _finish)
		//	{
		//		*(begin - 1) = *begin;
		//		begin++;
		//	}
		//	_finish--;
		//}



		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			_finish--;
			return pos;
		}



		//[]访问
		//返回可修改的引用，支持读写操作
		T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];
		}
		//支持读取操作但不能修改。
		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}
//返回类型为T&有以下几个原因：
//方便读写操作

	private:
		iterator _start=nullptr;//这个成员变量指向动态数组中第一个实际存储元素的内存位置。[
		iterator _finish=nullptr;//指向当前已填充元素的末尾，即最后一个有效元素的下一个位置。)
		iterator _endofstorage=nullptr;//指向动态数组的末尾，即分配的内存块的最后一个位置。
		// 1    2    3     4     空    空 
		// ↑_start				↑	   ↑：_endofstorage
		//					_finish
	};


	void print_vector(const vector<int>& v)
	{
		//此处为什么不能用范围for？   
		//因为const vector<int>& v 是const，迭代器也要用const的，所以要有const的begin和end
		for (auto e : v) 
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

在这里插入图片描述
📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
本人也很想知道这些错误，恳望读者批评指正！

阅读全部

相关推荐

  5. python实战（输出会动的爱心）*

    2024-07-15 10:34:03       19 阅读

  7. Go语言实现跳动的爱心（附带源码）

    2024-07-15 10:34:03       53 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-15 10:34:03       66 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-15 10:34:03       70 阅读

  9. 在Django里面运行非项目文件

    2024-07-15 10:34:03       57 阅读

  19. Python语言-面向对象

    2024-07-15 10:34:03       68 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-15 10:34:03       62 阅读

热门阅读

  4. [C++]位图+布隆过滤器

    2024-07-15 10:34:03       24 阅读

  6. GESP CCF C++ 五级认证真题 2024年6月

    2024-07-15 10:34:03       27 阅读

  7. 使用Python实现携程并发处理

    2024-07-15 10:34:03       24 阅读

  11. 明白了这点才能学好编程，否则参加什么培训班都没用

    2024-07-15 10:34:03       24 阅读

  16. 为什么请求接口会在后面接?_t=

    2024-07-15 10:34:03       19 阅读

  21. Why does Wi-Fi consume more battery power than cellular data?

    2024-07-15 10:34:03       23 阅读

  23. shell中关于数组的使用

    2024-07-15 10:34:03       23 阅读