揭秘Vector的三指针内存管理模型

用户11831438

发布于 2025-12-30 14:04:35

1210

一. Vector的神经中枢：三指针内存管理模型

Vector 本质上是一个能够动态增长的数组，其核心是通过三个指针（迭代器）控制内存块：

_start：指向开头位置的迭代器；
_finish：指向最后一个数据的下一个位置的迭代器；
_end_of_storage：指向结束空间位置的下一个位置的迭代器。

vector.h

namespace carrot
{
	template<class T>
	class vector
	{
	public:
		//typedef T* iterator;
		//C++11中提供了一个新的写法
		using iterator = T*;//iterator的类型就是T*
	private:
		iterator _start;//_start指向开头的迭代器（可以认为_start是指向开头的指针）
		iterator _finish;//_finish是指向最后一个有效数据的下一个位置
		iterator _end_of_storage;//指向最大空间的下一个位置
	};
}

这里的迭代器是用指针实现的。

注意：模板不能进行声明和定义分离，若分离会导致链接错误（原因后面介绍）！！！

1.1 理解容量与大小：size与capacity的解析

通过这三个指针，可直接计算：

有效元素个数（size）：_finish - _start
容量（capacity）：_end_of_storage - _start

public:
	//求出有效数据个数
	size_t size() const
	{
		return _finish - _start;
	}
	//空间大小
	size_t capacity() const 
	{
		return _end_of_storage - _start;
	}

二. 迭代器设计：连续内存的 “天然优势”

vector的迭代器是对原生指针的封装，支持随机访问等操作，是很好用的

2.1 迭代器的实现

public:
	//typedef T* iterator;
	//C++11中提供了一个新的写法
	using iterator = T*;//iterator的类型就是T*
	using const_iterator = const T*;
	//迭代器
    iterator begin()
    {
	    return _start;
    }
    iterator end()
    {
	    return _finish;
    }
    //const对象
    const_iterator begin() const
    {
	    return _start;
    }
    const_iterator end() const
    {
	    return _finish;
    }

2.2 [ ] ——运算符重载

public:
    //普通对象
	T& operator[](size_t pos)
	{
		return _start[pos];
	}
    //const对象
	T& operator[](size_t pos) const
	{
		return _start[pos];
	}

2.3 遍历+修改

vector.cpp

namespace carrot
{
	void print(const vector<int>& v)
	{
        //下标+[]
        for (size_t i = 0; i < v.size(); i++)
        {
	        cout << v[i] << " ";
        }
		//迭代器
		//vector<int>::const_iterator it= v.begin();
		auto it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		//范围for
		for (auto e : v)
		{
			cout << e << " ";
		}
        cout << endl;
	}
}

三. 核心接口实现：从构造到析构的内存管理

3.1 构造与析构：vector的基础框架

这里先介绍无参构造，无参构造是我们在实战过程中经常使用的一个构造，ok，话不多说，直接上代码。

vector.h

public:
	//构造
	//无参构造
	vector()
		:_start(nullptr)
		,_finish(nullptr)
		,_end_of_storage(nullptr)
	{}
	//析构
    ~vector()
    {
	    if (_start)
	    {
		    delete[] _start;
		    _start = _finish = _end_of_storage;
	    }
    }

3.2 容量管理：reserve 与 resize 的区别

3.2.1 reserve：仅扩容，不初始化空间

reserve(n) 保证容量至少为 n，仅当 n>capacity 时才分配新内存，不改变 size

这写的代码正确吗？其实是不正确的，那为什么不正确？

vector.h(正确代码)

//reserve
void resreve(size_t n)
{
	if (n > capacity())
	{
		sizt_t sz = size();
		T* tmp = new T[n];
		//空间中有数据才进行拷贝
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * sz);
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

3.2.2 resize 改变size：可能初始化或销毁元素

resize(n，val) 会将 size 调整为 n ，多余元素销毁，不足则用 val 填充

//resize
void resize(size_t n, T val = T())
{
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish != _start+n)
		{
			*_finish = val;
			++_finish;
		}
	}
}

那1这个内置类型是怎么形成匿名对象的？

这是因为在C++11中做了升级：内置类型也有默认构造（偏向于0的位置初始化）和析构

3.3 元素操作：增删查改的实现细节

3.3.1 尾插(push_back)与尾删(pop_back)

3.3.1.1 尾插(push_back)

当空间足够时，直接进行尾插操作；当空间不够时，先扩容，再进行尾插操作。

vector.h

public:
    //push_back
    void push_back(const T& val)
    {
	    //空间不够，扩容
	    if (_finish == _end_of_storage)
	    {
		    reserve(capacity() == 0 ? 4 : 2 * capacity());
	    }
	    //空间足够，直接插入
	    *_finish = val;
	    ++_finish;
    }

3.3.1.2 尾删(pop_back)

直接让_finish--即可

//pop_back
void pop_back()
{
	_finish--;
}

3.3.2 插入（insert）：中间插入的性能代价

在中间进行插入是一个代价很大的操作，因为要进行挪数据的操作，时间复杂度就是O(n)

有了前面string 的基础，我么可以很快写出相应的代码：

这~~代码正确吗？

我们插入数据运行一下：

嗯？为什么会出现随机值呢？ 这是因为：扩容后end是新空间的，而pos还是旧空间的，旧空间已经释放，pos指向的是一个随机值，pos迭代器失效

所以我们要让pos也成为新空间中的迭代器

我们接着看

auto it = v.begin() + 3;
v.insert(it, 30);

当我们执行上面这段代码时，insert以后，it会失效吗？

insert以后，it会失效，因为it是实参，形参的改变不影响实参，所以迭代器会失效

但是会有UU说，但是不一定扩容，若不扩容，it不失效；扩容，it失效。但是我们不知道什么时候扩容，所以无论扩不扩容，我们都认为it失效

所以，当我们想继续使用it迭代器，我们就需要返回新加入数据所在位置的迭代器，这也是vector库中的解决办法。

正确代码：

iterator insert(iterator pos, const T& val)
{
	assert(pos >= _start && pos < _finish);
	size_t len = pos - _start;
	//空间不够，扩容
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
	//空间足够，先挪数据，再插入
	iterator end = _finish - 1;
	pos = _start + len;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = val;
	++_finish;
	return pos;
}

注意：pos位置就是新加入数据所在位置的迭代器！！！

3.3.3 任意位置的删除（erase）

erase的作用是删除任意位置上的数据，并且使用迭代器传位置

auto it = v.end() - 1;
v.erase(it);

erase后，it失效吗？失效，指向了随机值

ok，若此时我们想在一组数据中删除偶数，保留奇数，我们就可以使用erase

void testVector3()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	v.push_back(5);
	print(v);
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
		++it;
	}
	print(v);
}

嗯？不是删除所有偶数吗？怎么还有偶数？为什么会这样？ 其实这还是迭代器失效的原因

那我们该怎么解决这个问题呢？我们可以让erase返回刚刚删除位置的下一个迭代器，这样就可以解决了

erase正确代码：

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

void testVector3()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	v.push_back(5);
	print(v);
	auto it = v.end() - 1;
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it=v.erase(it);
		}
		else
		{
			++it;
		}
	}
	print(v);
}

运行结果：

3.4 深拷贝的核心：实现拷贝构造与赋值重载

3.4.1 拷贝构造

问题：浅拷贝的陷阱

如果不实现拷贝构造，编译器会生成默认的拷贝构造，进行浅拷贝：

// 错误示例：浅拷贝导致双重释放
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
vector<int> v2(v1);  // 浅拷贝！v2 和 v1 指向同一块内存
// 析构时会发生双重 delete[]，程序崩溃！

所以我们要实现深拷贝：

vector(const vector<T>& v)
{
	reserve(v.capacity());
	for (auto e : v)
	{
		push_back(e);
	}
}

但是上面的代码还是有一点小问题，当T为int时，没有问题；但是当T为自定义类型时，这里会进行赋值操作，自定义类型的赋值会调用拷贝构造，有点麻烦，所以我们可以写成引用的方式并加上const。

vector(const vector<T>& v)
{
	reserve(v.capacity());
	for (const auto& e : v)
	{
		push_back(e);
	}
}

这里有一个问题，我们知道拷贝构造是用一个已经创建的对象去初始化另一个要创建的对象，但是这里的reserve中要使用这个要创建的对象，但是这个要创建的对象中的_start ,_finish _end_of_storage没有初始化，会有一些问题

我们可以这样写：

public:
    vector()
    {}
private:
	iterator _start=nullptr;
	iterator _finish=nullptr;
	iterator _end_of_storage=nullptr;

ok,说完了拷贝构造，我们来介绍几个比较好用的构造方式：

3.4.2 initializer_list构造

可以使用 { } 括一组数据进行构造。

vector(initializer_list<T> il)
{
	reserve(il.capacity());
	for (const auto& e : il)
	{
		push_back(e);
	}
}

测试实例：

void testVector5()
{
	vector<int> v({ 1,2,3,4,5,6,7 });
	print(v);
}

运行结果：

3.4.3 使用迭代区间构造

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

不是vector的迭代器不支持 -，但支持+！！！

3.4.4 n个val值的构造

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

ok，当我们执行这句语句时可以正常运行：

void testVector5()
{
	vector<int> v(10u, 1);
	print(v);
}

但是当我们运行下面这句代码时，就出现问题：

这是为什么？这是因为：

所以我们可以按照这种写法进行构造：

vector<int> v(10u, 1);
vector<int> v(10,'x');

3.4.5 赋值运算符重载

编译器默认生成的赋值是浅拷贝，浅拷贝对于内置类型可以，但是对于内部有资源的自定义类型就要实现深拷贝。

//赋值重载
vector<T>& operator=(const vector<T>& v)
{
	clear();
	reserve(v.capacity());
	for (auto& e : v)
	{
		push_back(e);
	}
	return *this;
}

3.4.6 swap

交换内部资源即可！！！

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

调用方式：

void testVector5()
{
	vector<int> v(10u, 1);
	vector<int> v1({ 1,2,3,4,5,6,7 });
	v.swap(v1);
}

或者这么写：

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

void testVector5()
{
	vector<int> v(10u, 1);
	vector<int> v1({ 1,2,3,4,5,6,7 });
	swap(v,v1);
}

3.4.7 现代写法

1、拷贝构造

vector(const vector<T>& v)
{
	vector<T> tmp(v.begin(), v.end());
	swap(tmp);
}

2、赋值重载

vector<T>& operator=(vector<T>& tmp)
{
	swap(tmp);
	return *this;
}

3.5 vector中隐藏的bug

当我们插入4个string类时，没有任何问题：

void testVector6()
{
	vector<string> v;
	v.push_back("11111111111111");
	v.push_back("11111111111111");
	v.push_back("11111111111111");
	v.push_back("11111111111111");
	for (auto e : v)
	{
		cout << e << " ";
	}
}

但是当我插入第5个数据时，发生了报错：

void testVector6()
{
	vector<string> v;
	v.push_back("11111111111111");
	v.push_back("11111111111111");
	v.push_back("11111111111111");
	v.push_back("11111111111111");
	v.push_back("11111111111111");

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

这是什么原因？

不难看出应该是扩容出现了问题。

我们知道memcpy是浅拷贝，当我们运行到这

memcpy(tmp, _start, sizeof(T) * sz); delete[] _start;

tmp中是值拷贝后的结果，_start和tmp中的数据指向的还是同一块空间，当delete[] _start;后，存放数据的空间被释放，当tmp再去找数据时就找不到了！！！所以这里还是深浅拷贝的问题

解决方法：深拷贝

改后的reserve代码：

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * sz);//浅拷贝无法满足内部有资源的
			//深拷贝   下面其中选一个即可
			for (size_t i = 0; i < sz; i++)
			{
				tmp[i] = _start[i];//如果是string,调用的是string赋值深拷贝
			}
			//for (size_t i = 0; i < sz; i++)
			//{
			//	swap(tmp[i], _start[i]);// 如果是string，调用string的交换，交换资源指向
			//}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

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

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

vector