C++标准模板库（STL）——vector的模拟实现

2501_90523001

1131人浏览 · 2025-11-05 10:22:59

2501_90523001 · 2025-11-05 10:22:59 发布

C++标准模板库（STL）——vector的模拟实现

文章目录

C++标准模板库（STL）——vector的模拟实现

如果你之前已经啃下了string的底层原理，那么恭喜你，vector的底层学习将会顺利很多

vector的底层和string非常相似，都是基于动态数组的内存管理。不过vector能够储存任意类型数据，而string主要储存的是字符串，

博主之前的博客（vector的使用）详细讲解了迭代器失效，感兴趣的同学可以阅读一下，本文章只会进行粗略讲解

1、基础框架

1）命名空间

使用namespace VE 将vector类封装起来，避免和C++标准库中的std::vector产生命名冲突

2) 模板和迭代器设计

vector作为通用容器，可以储存int、string、自定义结构体等任意类型，为了实现这个功能，我们要使用C++的模板template

首先用 template 定义模板参数 T，T相当于一个类型占位符，后续使用时编译器会自动把它替换成具体类型。
再将T*重命名为iterator迭代器，打造遍历容器的工具

3）核心成员指针

vector的内存管理依赖三个指针_start,_finish,_endofstorage

_start，指向vector第一个元素的地址
_finish,指向vector中最后一个元素的下一个位置（有效元素的尾后）
_endofstorage,指向vector底层已经开辟空间的尾后位置
其中[ _start, _finish )是有效元素区间，区间长度就是容器元素的个数（size）
[ _start, _endofstorage )是已开辟的内存空间，区间长度就是容器的容量（capacity）

在这里插入图片描述

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

/模板的声明和定义不能分离到两个文件中 .h .cpp

namespace VE
{
	/模板类
	template<class T>
	class vector
	{
	public:
		typedef T* iterator; /普通迭代器
		typedef const T* const_iterator; /常量迭代器
	private:
		iterator _start = nullptr; /元素的起始地址
		iterator _finish = nullptr; /有效元素的尾后地址
		iterator _endofstorage = nullptr; /底层空间的尾后地址
	};
}

2、迭代器接口和基础接口

接口是类对外提供的功能入口，相当于遥控器，用户可以直接使用接口，实现某种操作

1）迭代器接口

begin()、end()

迭代器是C++容器通用的遍历工具，迭代器的底层就是指针或者指针的封装。由于vector的底层是连续内存，所以迭代器直接使用原生指针T*实现，这也是vector迭代器支持随机访问的原因
代码设计还应该遵循 C++ 迭代器的 “左闭右开” 原则[begin(), end()）

/迭代器接口
/普通迭代器，支持读写
iterator begin()
{
	return _start;/返回第一个元素的地址
}
iterator end()
{
	return _finish;/返回有效元素的尾后位置
}
		
/常量迭代器，只支持读
const_ierator begin() const
{
	return _start;
}

const_iterator end() const
{
	return _finish;
}

2) 基础接口

size()、capacity()、empty()、operator[]

/基础属性接口
/获取有效元素个数
size_t size() const
{
	return _finish - _start;
}
		
/获取容量
size_t capacity() const
{
	return _endofstorage - _start;
}
	
/判断是否为空
bool empty() const
{
	return _start == _finish; / 起始地址 == 尾后地址，说明没有元素
}

/下标访问，支持修改元素
T& operator[](size_t i)
{
	assert(i < size());
	return _start[i];
}

/下标访问const，只能读取
const T& operator[](size_t i) const
{
	assert(i < size());
	return _start[i];
}

3、 vector的构造

1）默认构造函数

/传统默认构造
/ vector()
/ {}

/强制编译器生成默认构造（C++11）
vector() = default;

2）初始化列表构造（C++11）

initializer_list是C++11标准库提供的新容器，可以接收{}括起来的初始化列表，让初始化更方便了

/初始化列表构造（C++11）
/支持VE::vector<int> v={1,2,3};
vector(initializer_list<T> i1)
{
	/提前预留足够空间
	reserve(i1.size());

	/遍历初始化列表，逐个将元素尾插入vector
	for (auto& e : i1)
	{
		push_back(e);
	}
}

3）拷贝构造函数

vector储存的是元素本身，拷贝时需要深拷贝，复制所有元素再拷贝到新对象中。
避免浅拷贝（只赋值三个指针），避免让两个vector指向同一块空间

/拷贝构造函数
vector(const vector<T>& v)
{
	reserve(v.capacity()); /分配和v相同的容量
	/读取v中的元素值，然后将这个值拷贝到新对象的内存中
	for (auto& e : v)
	{
		push_back(e);
	}
}

4）迭代器范围构造函数

迭代器范围构造函数，可以获取别的容器string，list等的一段元素，直接生成我们的vector对象
使用模板函数，可以接收任意类型的迭代器，让vector可以接收任意类型的元素, 实现一函数多用

/模板函数：支持任意类型的迭代器
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);/取迭代器指向的元素，尾插入新对象
		++first;
	}
}

使用场景
在这里插入图片描述

5） n个相同元素的构造

T()是啥？
T（）表示创建一个T类型的默认值。
如果T是内置类型，T（）是“零值”，比如int()是0，double()是0.0，char()是’\0’
如果T是自定义类型，T（）会调用默认构造函数创建对象

为什么要设计两个版本？
如果只写size版本，当构造VE::vector v(5, 10); 时，
编译器会纠结，是将5（int类型）隐式转换成size_t，10传给val。还是把5，10当成两个int*类型的迭代器，匹配到vector(InputIterator first, InputIterator last)，这种情况下编译器会报歧义错误
添加int版本后，传入int类型会优先匹配int版本，这样就不会触发迭代器构造的歧义了

/创建包含n个val元素的vector，size版本
vector(size_t n, T val = T())
{
	resize(n, val); /复用resize的逻辑
}

/int版本
vector(int n, T val = T())
{
	reserve(n, val);
}

使用场景
在这里插入图片描述

4、析构函数

/析构函数
~vector()
{
	if (_start)
	{
		delete[]_start;  /释放动态分配的数组
		_start = _finish = _endofstorage = nullptr; /指针置空避免野指针
	}
}

5、赋值运算符重载

直接使用std::swap会触发三次深拷贝，效率很低
自定义的swap，仅 1 次深拷贝（值传递时）+交换三个指针成员效率很高

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)
{
	/与临时对象进行资源交换
	swap(v);
	return *this;
}

6、 vector的动态操作

1) reserve

分配新空间->拷贝旧元素->释放旧空间->更新指针

/扩容操作
void reserve(size_t n)
{
	/只有n大于当前容量才扩容
	if (n > capacity())
	{
		/记录旧元素个数
		size_t old_size = size();
		/分配新空间
		T* tmp = new T[n];
		/原空间非空，需要拷贝元素
		if (_start)
		{
			/不使用memcpy，它只是浅拷贝
			for (size_t i = 0; i < old_size; i++)
			{
				/对于自定义类型，调用T的赋值运算符或者拷贝构造，完成深拷贝
				/对于内置类型，等价于二进制拷贝，没有额外开销
				tmp[i] = _start[i];
			}
			delete[]_start;
		}
		/更新指针指向
		_start = tmp;
		_finish = _start + old_size;
		_endofstorage = _start + n;
	}
}

2）resize

/resize
void resize(size_t n, T cal = T())
{
	/如果n大于当前size，需要扩容
	if (n > size())
	{
		reserve(n);
		/从finish开始填充val,直到size为n
		while (_finish != _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
	/如果n小于当前size，直接截断不释放内存
	else
	{
		_finish = _start + n;
	}
}

3) push_back、pop_back

/尾插
void push_back(const T& x)
{
	/检查空间是否足够
	if (_finish == _endofstorage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}

	*_finish = x;
	++_finish;
}

/尾删
void pop_back()
{
	/确保容器非空
	assert(!empty());
	--_finish;
}

4) insert

要注意扩容导致的迭代器失效！

如果插入时触发扩容，原 pos迭代器指向的是已释放的旧空间，变成野指针，后续使用会程序崩溃。要记录扩容前的pos与_start的偏移量，扩容后给pos重新赋值，让新pos指向新空间

/指定位置插入数据
/返回新元素的迭代器，避免迭代器失效
iterator inset(iterator pos, const T& x)
{
	/检查pos合法性
	assert(pos >= _start && pos <= _finish);
	if (_finish == _endofstorage)
	{
		/扩容后原pos会失效
		size_t len = pos - _start;/记录pos与staert的距离，用于更新pos
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len; /更新pos
	}

	/从后往前挪动元素，给x留空间
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x; /插入新元素
	++_finish; /更新finish
	return pos; /返回指向新元素的迭代器
}

5） erase

注意被删除的pos的迭代器以及pos之后的所有迭代器均失效
解决方法，返回 “删除元素下一个位置的迭代器”，删除后用返回值更新迭代器，避免失效

		/删除指定位置元素
		iterator erase(iterator pos)
		{
			/检查pos合法性
			assert(pos >= _start && pos < _finish);

			/从pos+1开始，元素依次向前挪动一位
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			/更新finish，不释放内存
			--_finish;
			/返回指向删除元素的下一个位置的迭代器
			return pos;
		}

6） clear

	/清空
	void clear()
	{
		/ 只需要将finish移到start，逻辑清空（不释放容量）
		_finish = _start;
	}

7、检测代码正确性

其实应该写一段代码，就检测一段代码的正确性，为了方便阅读，我将测试用例都写在一起了

#define _CRT_SECURE_NO_WARNINGS 1
#include"vector.h"

/默认构造，尾插，下标访问
void test1()
{
	VE::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	cout << v1 << endl;
	v1.push_back(5);
	cout << v1 << endl;
	cout <<"v1[2]:" << v1[2] << endl;
	 输出：1 2 3 4
	1 2 3 4 5
	v1[2]:3
}

/各种构造
void test2()
{
	/初始化列表构造
	VE::vector<int> v2 = { 1,2,3,4 };
	cout << v2 << endl;
	VE::vector<string>v3 = { "apple", "banana", "orange" };
	cout << v3 << endl;
	/填充构造
	VE::vector<int> v4(3, 100);
	cout << v4 << endl;

	/迭代器范围构造
	int arr[] = { 10,20,30 };
	VE::vector<int> v5(arr, arr + 3);
	VE::vector<int> v6(v2.begin() + 1, v2.end() - 1);
	cout << v5 << endl;
	cout << v6 << endl;
	/输出：1 2 3 4
	/apple banana orange
	/	100 100 100
	/	10 20 30
	/	2 3
}

/拷贝构造 + 赋值运算符
void test3()
{
	VE::vector<int> v1 = { 1,2,3,4 };
	VE::vector<int> v2(v1);
	VE::vector<int> v3 = { 1 };
	v3 = v1;
	cout << v2 << endl;
	cout << v3 << endl;
	/输出：1 2 3 4
	/1 2 3 4

}

/insert erase 
void test4()
{
	VE::vector<int> v1 = { 1,2,3,4 };
	auto it = v1.insert(v1.begin() + 2, 99);
	cout << v1 << endl;
	
	it = v1.erase(v1.begin() + 2);
	cout << v1 << endl;
/输出：	1 2 99 3 4
/	1 2 3 4
}

/pop_back clear empty
void test5()
{
	VE::vector<int> v1 = { 1,2,3,4 };
	v1.pop_back();
	cout << v1 << endl;
	v1.clear();
	cout << v1 << endl;
	cout << "v1是否为空: " << (v1.empty() ? "是" : "否") << endl;
	/输出：1 2 3
	/
	/	v1是否为空: 是
}

/resize reverse
void test6()
{
	VE::vector<int> v1;
	v1.reserve(10);
	cout << v1 << endl;
	v1.resize(5, 99);
	cout << v1 << endl;
	v1.resize(3);
	cout << v1 << endl;
/输出：
	/	99 99 99 99 99
	/	99 99 99
}
int main()
{
	/test1();
	/test2();
	/test3();
	/test4();
	/test5();
	test6();
	return 0;
}

8、完整代码

vector.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

//模板的声明和定义不能分离到两个文件中 .h .cpp

namespace VE
{
	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;
		}

		//基础属性接口
		//获取有效元素个数
		size_t size() const
		{
			return _finish - _start;
		}

		//获取容量
		size_t capacity() const
		{
			return _endofstorage - _start;
		}

		//判断是否为空
		bool empty() const
		{
			return _start == _finish;// 起始地址 == 尾后地址，说明没有元素
		}

		//下标访问，支持修改元素
		T& operator[](size_t i)
		{
			assert(i < size());
			return _start[i];
		}

		//下标访问const，只能读取
		const T& operator[](size_t i) const
		{
			assert(i < size());
			return _start[i];
		}
		
		//传统默认构造
		// vector()
		// {}

		//强制编译器生成默认构造（C++11）
		vector() = default;



		//初始化列表构造（C++11）
		//支持VE::vector<int> v={1,2,3};
		vector(initializer_list<T> i1)
		{
			//提前预留足够空间
			reserve(i1.size());

			//遍历初始化列表，逐个将元素尾插入vector
			for (auto& e : i1)
			{
				push_back(e);
			}
		}


		//拷贝构造函数
		vector(const vector<T>& v)
		{
			reserve(v.capacity());//分配和v相同的容量
			//读取v中的元素值，然后将这个值拷贝到新对象的内存中
			for (auto& e : v)
			{
				push_back(e);
			}
		}

		//模板函数：支持任意类型的迭代器
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);//取迭代器指向的元素，尾插入新对象
				++first;
			}
		}

		//创建包含n个val元素的vector，size版本
		vector(size_t n, T val = T())
		{
			resize(n, val);//复用resize的逻辑
		}

		//int版本
		vector(int n, T val = T())
		{
			resize(n, val);//复用resize
		}

		//析构函数
		~vector()
		{
			if (_start)
			{
				delete[]_start; //释放动态分配的数组
				_start = _finish = _endofstorage = nullptr;//指针置空避免野指针
			}
		}

		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)
		{
			//与临时对象进行资源交换
			swap(v);
			return *this;
		}

		//扩容操作
		void reserve(size_t n)
		{
			//只有n大于当前容量才扩容
			if (n > capacity())
			{
				//记录旧元素个数
				size_t old_size = size();
				//分配新空间
				T* tmp = new T[n];
				//原空间非空，需要拷贝元素
				if (_start)
				{
					//不使用memcpy，它只是浅拷贝
					for (size_t i = 0; i < old_size; i++)
					{
						//对于自定义类型，调用T的赋值运算符或者拷贝构造，完成深拷贝
						//对于内置类型，等价于二进制拷贝，没有额外开销
						tmp[i] = _start[i];
					}
					delete[]_start;
				}
				//更新指针指向
				_start = tmp;
				_finish = _start + old_size;
				_endofstorage = _start + n;
			}
		}


		//resize
		void resize(size_t n, T val = T())
		{
			//如果n大于当前size，需要扩容
			if (n > size())
			{
				reserve(n);
				//从finish开始填充val,直到size为n
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			//如果n小于当前size，直接截断不释放内存
			else
			{
				_finish = _start + n;
			}
		}

		//尾插
		void push_back(const T& x)
		{
			//检查空间是否足够
			if (_finish == _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			*_finish = x;
			++_finish;
		}

		//尾删
		void pop_back()
		{
			//确保容器非空
			assert(!empty());
			--_finish;
		}

		//在指定位置插入数据
		//返回新元素的迭代器，避免迭代器失效
		iterator insert(iterator pos, const T& x)
		{
			//检查pos合法性
			assert(pos >= _start && pos <= _finish);
			if (_finish == _endofstorage)
			{
				//扩容后原pos会失效
				size_t len = pos - _start;//记录pos与staert的距离，用于更新pos
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len; //更新pos
			}

			//从后往前挪动元素，给x留空间
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;//插入新元素
			++_finish;//更新finish
			return pos;//返回指向新元素的迭代器
		}

		//删除指定位置元素
		iterator erase(iterator pos)
		{
			//检查pos合法性
			assert(pos >= _start && pos < _finish);

			//从pos+1开始，元素依次向前挪动一位
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			//更新finish，不释放内存
			--_finish;
			//返回指向删除元素的下一个位置的迭代器
			return pos;
		}

		//清空
		void clear()
		{
			// 只需要将finish移到start，逻辑清空（不释放容量）
			_finish = _start;
		}
	private:
		iterator _start = nullptr;//元素的起始地址
		iterator _finish = nullptr;//有效元素的尾后地址
		iterator _endofstorage = nullptr;//底层空间的尾后地址
	};


	//输出
	template<class T>
	ostream& operator<<(ostream& os, const vector<T>& v)
	{
		for (size_t i = 0; i < v.size(); i++)
		{
			os << v[i]<<" ";
		}
		return os;
	}
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"vector.h"

//默认构造，尾插，下标访问
void test1()
{
	VE::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	cout << v1 << endl;
	v1.push_back(5);
	cout << v1 << endl;
	cout <<"v1[2]:" << v1[2] << endl;
	/*输出：1 2 3 4
	1 2 3 4 5
	v1[2]:3*/
}

//各种构造
void test2()
{
	//初始化列表构造
	VE::vector<int> v2 = { 1,2,3,4 };
	cout << v2 << endl;
	VE::vector<string>v3 = { "apple", "banana", "orange" };
	cout << v3 << endl;
	//填充构造
	VE::vector<int> v4(3, 100);
	cout << v4 << endl;

	//迭代器范围构造
	int arr[] = { 10,20,30 };
	VE::vector<int> v5(arr, arr + 3);
	VE::vector<int> v6(v2.begin() + 1, v2.end() - 1);
	cout << v5 << endl;
	cout << v6 << endl;
	//输出：1 2 3 4
	//apple banana orange
	//	100 100 100
	//	10 20 30
	//	2 3
}

//拷贝构造 + 赋值运算符
void test3()
{
	VE::vector<int> v1 = { 1,2,3,4 };
	VE::vector<int> v2(v1);
	VE::vector<int> v3 = { 1 };
	v3 = v1;
	cout << v2 << endl;
	cout << v3 << endl;
	//输出：1 2 3 4
		//1 2 3 4

}

//insert erase 
void test4()
{
	VE::vector<int> v1 = { 1,2,3,4 };
	auto it = v1.insert(v1.begin() + 2, 99);
	cout << v1 << endl;
	
	it = v1.erase(v1.begin() + 2);
	cout << v1 << endl;
//输出：	1 2 99 3 4
	//	1 2 3 4
}

//pop_back clear empty
void test5()
{
	VE::vector<int> v1 = { 1,2,3,4 };
	v1.pop_back();
	cout << v1 << endl;
	v1.clear();
	cout << v1 << endl;
	cout << "v1是否为空: " << (v1.empty() ? "是" : "否") << endl;
	//输出：1 2 3
	//
	//	v1是否为空: 是
}

//resize reverse
void test6()
{
	VE::vector<int> v1;
	v1.reserve(10);
	cout << v1 << endl;
	v1.resize(5, 99);
	cout << v1 << endl;
	v1.resize(3);
	cout << v1 << endl;
//输出：
	//	99 99 99 99 99
	//	99 99 99
}
int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	test6();
	return 0;
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

GitHub今日热榜 | 2026-08-06

今日榜单呈现大换血，10个项目中7个为新晋项目。Cloudflare的Agent虚拟环境项目computer空降榜首，提供隔离文件系统和多执行后端支持。腾讯的TencentDB-Agent-Memory虽排名下滑至第3，但日增Star上涨70%。其他亮点包括： loopx为AI Agent团队提供看板管理系统经典面试指南system-design-primer回归榜单 DeepSeek-Reas