C++:手把手教你手撕vector

啊QQQQQ

发布于 2025-02-20 08:38:18

7800

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

一,打开vs2022,创建项目文件

二, 创建源文件和测试文件

vector.hpp是源文件里面是vector的实现,main函数是测试用的,因为一个项目只能有一个main入口对吧;

这时候就有人说了,为什么vector文件的后缀是hpp呢?

------------------->.h是头文件里面是需要的宏和函数声明,以及其他头文件;.cpp是C++源文件,所以,懂了吧!没错,hpp就是h和cpp的合体,我们直接把声明和实现一块写了,没有分开实现;就这样简单!

三,准备工作-头文件包含,命名空间定义

首先我们需要在vector.hpp文件中的最顶部写上语句#pragma once

什么意思?

#pragma once 就是在其他每个文件中只能被包含一次,不可被重复包含;

#pragma once 可以看成是#ifndf ..... #endif;

3.1头文件

接下来就是引入所需要的头文件了(这里可能引入几个没有用到,问题不大!);

#pragma once 
#include<iostream>
#include<cstdlib>
#include<assert.h>
#include<string>
#include<algorithm>
#include<vector>

3.2vector<T>类

因为库中是存在std::vector,为了避免冲突,所以我们可以换个命名空间实现我们自己的vector;这里我的命名空间,不过,我这里没有展开std,所以没有问题;直接写类函数就可以了;

然后我们在命名空间中把vector实现了,需要封装起来,不要忘记vector是个模版哦!

#pragma once 
#include<iostream>
#include<cstdlib>
#include<assert.h>
#include<string>
#include<algorithm>
#include<vector>
template<class T>
class vector
{
};

Alloc是内存池,编译器有关系,自动分配内存的;不要慌,我们也学过自己开内存的函数不是吗?

没错在C语言中我们学过malloc,free,在C++中我们学过new ,delete ;

提都提到了,不妨说一下两者的区别?

1.从本身种类来说:

malloc和free是函数,而new和delete是操作符;

2.使用方面

malloc就是直接开辟空间,但是malloc的返回值是void*,所以我们每次使用几乎都需要强制转化;

new 底层是封装的malloc,不需要强转返回值类型,而且,new开辟空间的同时会调用对象的构造函数;

开空间时malloc需要指明开辟空间的大小字节数,而new直接知道对下对象的个数就可以了;

free是释放指针指向的内存,delete释放内存的同时也会调用对象的析构函数;

delete释放数组时 delete [ ]array;free无区别;

四,开始实现接口

在此之前我们需要先了解下官方的vector底层成员变量是什么;

打开文档:vector - C++ Reference

这里我直接告诉大家了:

	iterator _start; 
	iterator _finish;
	iterator _end_of_storage;

成员变量是迭代器;

迭代器怎么封装呢?

我们知道迭代器类似于指针类型;所以我们就用T* 模拟了;

#pragma once 
#include<iostream>
#include<cstdlib>
#include<assert.h>
#include<string>
#include<algorithm>
#include<vector>
template<class T>
class vector
{
	typedef T* iterator;
	typedef const T* const_iterator;     
 public:
private:
	iterator _start; 
	iterator _finish;
	iterator _end_of_storage;
};

4.1size(),capacity(),begin(),end()

const_iterator begin()const
{
	return _start;  
}
const_iterator end()const
{
	return _finish;
}
iterator  begin()
{
	return _start; 
}
iterator end()
{
	return _finish;  
}
int size()const
{
	return _finish - _start; 
}
int capacity()const
{
	return _end_of_storage - _start; 
}
int size()
{
	return _finish - _start; 
}
int capacity()
{
	return _end_of_storage - _start; 
}

这些比较简单,直接pass

4.2reserve函数

	void reserve(size_t n)
	{
		if (n > capacity())
		{
			int oldsize = size();
			T* tmp = new int[n]; 
			if (_start) { 
				memcpy(tmp, _start, sizeof(T) * size());
				delete _start;
			}
			_start = tmp;
			_finish = _start + oldsize;
			_end_of_storage = tmp + n;
		}
	}

reserve函数是扩容的;也就是改变_end_od_storage最多元素的个数;

这里的逻辑是:如果n大于当前的capacity就需要扩容了

怎么扩容呢?

我们需要另外开大小是n的空间,然后将当前的数据拷贝过去,不要忘记了吧_finish和_end_of_storage更新了;

这个时候就出现问题了;我们要更新_finish就需要知道当前元素的个数,不出意料我们会直接调用函数size获取,这样就跳进坑里了!

为什么?

size()->_finish-_start;看出来了吗,我现在要更新_finish,却使用了_finish,岂不荒唐?size()这时候里面的_finish/还是老地址的_finish,而现在_start已经是新地址了,他们根本就不在同一块空间上!

所以我们需要更新_start之前,先记录_finish距离_start的偏移量;

4.3push_back函数

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

因为要改变数组容量,所以需要检查是否需要扩容,如果是第一次尾插那capacity()就是0;我们给4个整形;如果capacity不是0,那就扩大一倍;

4.4operator[]

	T& operator [] (size_t n)
	{
		return _start[n]; 
	}
	const T& operator[](size_t n)const
	{
		return _start[n]; 
	}

4.5现代swap

	void swap(vector<int>& v)
	{
		std::swap(_start,v._start);
		std::swap(_finish, v._finish);
		std::swap(_end_of_storage,v._end_of_storage);
	}

我们要交换数据,直接成员即可;

4.6operator=(夺舍)

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

这个就有说法了,我们知道形参是拷贝的临时变量;那么我们就可以在他释放前把他的数据夺过来,这样我获取的他的数据,不就是拷贝吗?我的数据给他,会自动释放掉;对吧?没毛病;

4.7pop_back()

	void pop_back()
	{
		--_finish; 
	}

4.8.insert

	iterator insert(iterator pos, const T& x)
	{
		assert(pos >= _start);
		assert(pos <= _finish);
		if (_finish == _end_of_storage)
		{
			int index = pos - _start;//后序_start会变化
			size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
			pos = _start + index; //转化当前的_start中  
		}
		iterator end = _finish - 1; 
		while (end >= pos)
		{
			*(end + 1) = *end; 
			end--; 
		}
		*pos = x;    
		_finish++; 
		return pos;     
	}

类似于顺序表,需要注意的还是更新旧地址指针;

4.9erase

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

	}

4.10构造系列

	vector()
	{
		_start = nullptr; 
		_finish = nullptr; 
		_end_of_storage = nullptr; 
	}
	vector(const vector<T>& v)
	{
		reserve(v.size());
		for (auto x : v)
			push_back(x);
	}
	vector(size_t n, const T& val ) 
	{
		reserve(n);
		for (int i = 0; i < n; i++)
			push_back(val); 
	}
	//迭代器区间拷贝
	template <class InputIterator > 
	vector(InputIterator  first, InputIterator last)
	{
		while (first != last)
		{
			push_back(*first);
			first++; 
		}
	}

五,迭代器失效问题

我们一旦发生扩容就会发生迭代器失效问题,为什么?

在 std::vector 中使用 erase 操作后原迭代器失效，主要有以下原因： - 重新分配可能内存： std::vector 在元素数量发生变化时，可能需要重新分配内存以保证足够的空间存储元素。当执行 erase 操作后，如果 vector 的元素数量大幅减少，可能会触发内存收缩，导致所有元素被移动到新的内存地址，那么原来的迭代器所指向的地址就不再有效。 - 元素移动：即使没有内存重新分配， erase 操作也会使后续元素向前移动来填补被删除元素的位置。迭代器本质上是一种指向容器中元素的“指针”，当元素位置发生改变后，原来指向被删除元素及之后元素的迭代器就不再指向原来意义上的元素了，如果继续使用，可能会访问到错误的数据或者导致程序崩溃。例如，假设迭代器 it 原本指向 vector 中的第三个元素，当删除第二个元素后，第三个元素向前移动到第二个位置， it 仍然指向原来第三个元素的地址，但该地址的内容已经改变，并且此时 it 所指向的逻辑上已经不是原来的第三个元素了，而是新的第二个元素，这就导致了迭代器失效。

整体源码

vector.hpp

#pragma once 
#include<iostream>
#include<cstdlib>
#include<assert.h>
#include<string>
#include<algorithm>
#include<vector>
template<class T>
class vector
{
	typedef T* iterator;
	typedef const T* const_iterator; 
	typedef vector initializer_list;     
 public:
	vector()
	{
		_start = nullptr; 
		_finish = nullptr; 
		_end_of_storage = nullptr; 
	}
	vector(const vector<T>& v)
	{
		reserve(v.size());
		for (auto x : v)
			push_back(x);
	}
	vector(size_t n, const T& val ) 
	{
		reserve(n);
		for (int i = 0; i < n; i++)
			push_back(val); 
	}
	//迭代器区间拷贝
	template <class InputIterator > 
	vector(InputIterator  first, InputIterator last)
	{
		while (first != last)
		{
			push_back(*first);
			first++; 
		}
	}
	const_iterator begin()const
	{
		return _start;  
	}
	const_iterator end()const
	{
		return _finish;
	}
	iterator  begin()
	{
		return _start; 
	}
	iterator end()
	{
		return _finish;  
	}
	int size()const
	{
		return _finish - _start; 
	}
	int capacity()const
	{
		return _end_of_storage - _start; 
	}
	int size()
	{
		return _finish - _start; 
	}
	int capacity()
	{
		return _end_of_storage - _start; 
	}
	void reserve(size_t n)
	{
		if (n > capacity())
		{
			int oldsize = size();
			T* tmp = new int[n]; 
			if (_start) { 
				memcpy(tmp, _start, sizeof(T) * size());
				delete _start;
			}
			_start = tmp;
			_finish = _start + oldsize;
			_end_of_storage = tmp + n;
		}
	}
	void push_back(int x)
	{
		if (_finish==_end_of_storage)
		{
			int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity); 
		}
		*_finish = x;
		_finish++;
	}
	T& operator [] (size_t n)
	{
		return _start[n]; 
	}
	const T& operator[](size_t n)const
	{
		return _start[n]; 
	}
	void swap(vector<int>& 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; 
	}
	~vector()
	{
		if (_start)
		{
			delete _start; 
			_start = _finish = _end_of_storage = nullptr; 
		}
	}
	void pop_back()
	{
		--_finish; 
	}
	iterator insert(iterator pos, const T& x)
	{
		assert(pos >= _start);
		assert(pos <= _finish);
		if (_finish == _end_of_storage)
		{
			int index = pos - _start;//后序_start会变化
			size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			reserve(newcapacity);
			pos = _start + index; //转化当前的_start中  
		}
		iterator end = _finish - 1; 
		while (end >= pos)
		{
			*(end + 1) = *end; 
			end--; 
		}
		*pos = x;    
		_finish++; 
		return pos;     
	}

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

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

main.cpp

#include "vector.hpp"

void test1()
{
	vector<int>v; 
	for (int i = 0; i < 4; i++)
		v.push_back(i);
	for (auto x : v)
		std::cout << x << " ";
	std::cout << v.capacity()<<v.size()<<std::endl;
	v.reserve(10);
	for (auto x : v)
		std::cout << x << " ";
	std::cout << v.capacity() << v.size() << std::endl;

	vector<int> v1(v.begin(),v.end());       
	auto it = std::find(v1.begin(), v1.end(), 3); 
	std::cout << *it << std::endl;   
	v1.insert(it, 1000); 
	auto it2 = std::find(v1.begin(), v1.end(), 3);


	v1.erase(it2);   
	for (auto x : v1)  
		std::cout << x << " ";
	std::cout << v1.capacity() << v1.size() << std::endl;
	v1.reserve(10);
	for (auto x : v1)
		std::cout << x << " ";
	std::cout << v1.capacity() << v1.size() << std::endl;
}

int main()
{
	test1();
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-19，如有侵权请联系 cloudcommunity@tencent.com 删除

内存