vector 模拟实现 4 大痛点解析：从 memcpy 到模板嵌套的实战方案

用户11862565

发布于 2025-10-13 15:33:33

1300

代码可运行

运行总次数：0

代码可运行

一、模拟实现vector

1.1 reserve的实现及其问题

reserve是vector预留/扩容的借口

下面我看下实现的这段代码是否正确

	//实际大小
	size_t size()
	{
		return _finish - _start;
	}

	//容量大小
	size_t capacity()
	{
		return _end_of_storage - _start;

	}
//预留/保留
void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		memcpy(tmp, _start, size() * sizeof(T));

		delete[] _start;
		_start = tmp;

		_finish = _start + size();
		_end_of_storage = _start + n;

	}
}

眨眼一看，发现没有任何问题，但是我们试试运行下代码来看看：

代码崩溃了，这是为什么？经过调试我们发现，在_finish调用size（）是错误的，因为start=tmp，已经指向了新空间，start已经不是0了，但是_finish是0，因此在调用size函数时则是_start+_finish(0)-_start=0，这就是空间的新老经典问题，size是扩容后的，_finish是扩容前的

解决方法：

可以先更新_finish,即_finish=tmp+size()
可以定义一个old_size=size()来存放旧空间的size

1.2 打印模板的实现

为了打印不同类型的vector，因此我们提供了模板

	template<class T>
	void print_vector(const vector<T>& v)
	{
		
		 vector<T>::const_iterator it = v.begin();
		auto it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

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

上述代码运行完后，我们发现编译报错，这又是为什么？

由于编译器编译是从上往下执行，编译到 vector::const_iterator it = v.begin()时，编译器不知道T是什么，因为类模板有个原则就是其没有被实例化前不会到类里面去取东西（编译器怕类里面会有各种坑），因此其无法判断是类型还是静态成员变量，因此编译器过不了。

解决方法：

typename vector::const_iterator it = v.begin();,加了typename后就代表其是类型
我们可以直接使用auto，让编译器自动推导其类型(由v.begin推导it类型)：auto it=v.begin()

1.3 迭代器失效

情况1：

我们来看下insert接口的实现，在测试案例中我们先使用不扩容的操作：

//插入
iterator insert(iterator pos, const T& x)
{
	// 扩容
	if (_finish == _end_of_storage)
	{

   reserve(capacity() == 0 ? 4 : capacity() * 2);

	}

	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;

	++_finish;

	return pos;
}

	void test_vector2()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		print_vector(v);

		v.insert(v.begin() + 2, 30);

		print_vector(v);
	}
}

结果演示：

我们再使用扩容的案例看看（去掉： v.push_back(5);，呕吼~我们发现代码是有问题的

这里就是经典的迭代器失效问题：由于finish=capacity，因此需要开新的空间tmp=2*原空间，并将start指向新空间，释放旧空间，但是pos还是指向旧空间，这就是类似野指针

解决方法： pos的含义我们可以理解成start和pos的相对位置，定义len表示pos和start的相对位置，扩完容后让pos=start+len，即可以表示新空间的pos所在的位置

情况2：

find查找如果我们期望输入x，在x之前插入数据，由于我们不知道x在哪个位置，这里我们就需要查找了，但是在官方的vector的官方文档里并没有提供查找的接口。

但是在C++算法里面提供了find接口，所有容器都可以使用

	int x;
	cin >> x;
	auto pos = find(v.begin(), v.end(), x);

	if (pos != v.end())
	{
		v.insert(pos, 40);
		(*pos)*=10;
	}
}

我们发现，我们在pos位置前插入40后，再让pos位置的值*10，但是我们发现结果是pos位置的值没有改变，但是40变成400了，这是为什么？

这里也可以理解成迭代器失效，这里insert完后，我们认为pos已经失效了，不要再访问了，因为pos指向的是旧空间，这里我们可能会说，在5.3中不是已经实现了相对位置，但是我们需要注意的是，形参的改变并不影响实参，因此pos还是指向旧空间（由于数据挪动，pos不是指向2，所以insert以后我们认为迭代器失效，不要访问）

如果我们实在想访问，我们可以更新下pos的位置再去访问，就如：pos=v.insert(pos,40);

if (pos != v.end())
{
	pos=v.insert(pos, 40);
	//
	(*(pos+1)) *= 10;
}

总结：迭代器失效分为两种情况 1.扩容导致的野指针 2.无扩容：位置意义已经变了（由于数据挪动）在vs2022上进行了强制检查，访问就会报错（需要更新迭代器），在gcc上则不会报错

1.4删除数据

删除pos当前位置的数据，就需要不断将pos+1位置的数据移动到pos上，直至结束

下面我们通过删除偶数数据来看看下面这段代码是否正确

//删除数据
void erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);
	iterator it = pos + 1;
	while (it != end())
	{
		*(it-1 ) = *(it);
		++it;
	}
	--_finish;
}

void test_vector3()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);


	//删除所有的偶数
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
		++it;
	}
	print_container(v);
}

结果演示：

这段代码通过了示例，那么是否没有问题？我们再想想迭代器失效的第二种情况，erase了还对迭代器进行各种访问真的正确吗？

下面我们给出如下示例：

偶数没有处理干净的代码演示：

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	v.push_back(5);

下面这种示例程序直接崩溃了

v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);

出现上述问题1：:如果给的示例是连续的偶数，如1 2 3 4 4 5，当pos走到2，因为是偶数，调用erase删除了2，并将pos++，pos跳过了3来到了4，因为4是偶数，删除数据并pos++来到5，这里直接跳过了第二个四，导致没删干净

问题：同样是因为++导致的，示例1 2 3 4，pos走到2，发现是偶数则++来到了4的位置，发现4也是偶数，那么删除4，finish- -，来到了4的位置，但是pos++，导致pos>finish,数组越界

1.5 resize 调整容器元素的数量

在进行容器元素数据调整时有三种情况： 1.当需要调整的容器数量n<size,则让_finish减少到n 2.size<n<capacity时，则尾插到数组中，即_finish=val 3.n>capacity时，则需扩容

	void resize(size_t n, const T& val = T())//调整大小
	{
		//三种情况
		//n<szie
		//size<n<capacity
		//n>capacity

		if (n < size())
		{
			_finish = _start + n;

		}
		else
		{
			reserve(n);
			while (_finish <_start+n)
			{
				*_finish = val;
				++_finish;
			}
		}

	}
		void test_vector4()
	{
		int i = int();
		int j = int(1);
		int k(2);


		vector<int> v;
		v.resize(10, 1);
		v.reserve(20);

		print_container(v);
		cout << v.size() << endl;
		cout << v.capacity() << endl;
    
    //这里只是让最后五个数据为2
		v.resize(15, 2);
		print_container(v);
	}

二、memcpy拷贝问题及木板嵌套问题

2.1 拷贝构造

下面我们通过拷贝构造来探究下：

void test_vector5()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	print_container(v);

	//拷贝构造
	vector<int> v1 = v;
	print_container(v1);
}

我们发现v和v1的地址是完全相同，那么它们是指向相同的空间，但是程序没有崩溃，这是因为我们没有写析构函数（系统默认的析构函数对指针不做释放处理，只销毁），因此除了手动写析构函数外，我们还需要手动写拷贝构造

		/*vector()
		{	}*/
		// C++11 强制生成默认构造
		vector() = default;

		vector(const vector<T>& v) 
		{
		
	   	   reserve(v.capacity());
	   	   
			for (auto& e : v)
			{
				push_back(e);
			}
		}
		
         	~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _end_of_storage = nullptr;

			}
		}

下面我们继续来看个memcpy导致的问题：

	void test_vector7()
	{
		vector<string> v;
		v.push_back("11111111111111111111111111");
		v.push_back("11111111111111111111111111");
		v.push_back("111111111111111111111111111");
		print_container(v);
		}

如下我们发现打印结果并没有出现问题

请不要眨眼，我们继续添加几组案例

void test_vector7()
{
	vector<string> v;
	v.push_back("11111111111111111111111111");
	v.push_back("11111111111111111111111111");
	v.push_back("111111111111111111111111111");
	print_container(v);

	v.push_back("1111111111111111111111");
	v.push_back("1111111111111111111111");
	print_container(v);
}

这时候我们发现结果出现乱码，这里显而易见是扩容导致的问题，经过调试我们发现是memcpy中delete[ ]时程序出了问题，由于vector里面存的是string，如下图·：

memcpy是一个字节一个字节的拷贝，把start指向的空间的值拷贝给tmp指向的值，因此tmp所指向的空间和其是一样位置（浅拷贝），也就是说vector是深拷贝，但是vector里面的string使用了memcpy导致了浅拷贝，导致delete[ ]调用析构函数，释放空间，将tmp空间置为随机值，因此会乱码

解决方法： 这里我们需要进行深拷贝，由于不同平台实现string不同，有的使用显示拷贝不能访问其内部数据，因此这里我们需要使用string的赋值重载[ ]（调用的是std::）即可解决（释放旧空间，拷贝值给新空间）

	void reserve(size_t n)
	{
		if (n > capacity())
		{
			size_t old_size = size();
			T* tmp = new T[n];
			//memcpy(tmp, _start, old_size * sizeof(T));
			for (size_t i = 0; i < old_size; i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;

			_start = tmp;
			_finish = tmp + old_size;
			_end_of_storage = tmp + n;
		}
	}

2.2 赋值

常规写法：

	void clear()
	{
		_finish = _start;
	}
	vector<T>& operator=(const vector<T>& v)
	{
		//判断自己给自己赋值
		if (this != &v)
		{
			clear();
			reserve(v.size());
			for (auto& e : v)
			{
				push_back(e);
			}
		}
		return *this;
	 }
		void test_vector5()
		{   
			vector<int> v3;
			v3.push_back(10);
			v3.push_back(20);
			v3.push_back(30);

			v1 = v3;
			print_container(v1);
			print_container(v3);
		}

现代写法（在string已经有所介绍）string

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<T>& operator=( vector<T> v)
 	{
    	swap(v);

	    return *this;
     }

2.3 模板嵌套问题

下面我们看下类模板嵌套函数模板的问题

       //类模板的成员函数，还可以继续时函数模板
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

在这段代码中外层是类模板：vector<T>，内层是成员函数模板vector(InputIterator first,InputIterator last)，那么为什么要这么设计？这是方便容器用其他容器的迭代器初始化，但是要求类型是匹配的（假设vector存的是string，给给list时候是double，这是不可以的）举个例子，在C语言中学到的链表排序，会有所复杂，但是把链表转换成vector则会简单很多

void test_vector6()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(4);
	v1.push_back(4);

	vector<int> v2(v1.begin(), v1.begin() + 3);
	print_container(v1);
	print_container(v2);

	list<int> lt;
	lt.push_back(10);
	lt.push_back(10);
	lt.push_back(10);
	lt.push_back(10);
	vector<int> v3(lt.begin(), lt.end());
	print_container(lt);
	print_container(v2);
	}