【c++】STL-vector容器的部分实现以及使用

mosheng

发布于 2026-01-14 18:27:44

1070

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

hello~ 很高兴见到大家! 这次带来的是C++中关于vector容器这部分的一些知识点,如果对你有所帮助的话,可否留下你的三连呢? 个人主页: 默|笙

它的使用与 string (关于string使用的一篇博客）非常相像，不过接口会精简很多。vector<—（可用来查询接口以及使用方法）。

一：基本框架构建

与string（专门存储字符的容器）不同，vector是通用动态数组，可存储满足复制 / 赋值要求的任意类型（如int、自定义类），并支持嵌套使用，如vector<vector>（本质是容器的容器，但在逻辑上可看作一个存储int类型数据的二维数组方便理解。
基本框架：

关于vector类的成员变量的创造，可以参考一部分STL源代码：

创建模板，为了能够将类型参数化，允许用户在实例化vector能够显式指定存储的数据类型。

代码：

namespace mosheng {
	template<class T>

	class vector
	{
	public:
		typedef T* iterator;//类型参数化的指针
		//size()
		size_t size()const
		{
			return _finish - _start;
		}
		//capacity()
		size_t capacity()const
		{
			return _endofstorage - _start;
		}
	private:
		iterator _start;//指向容器底层数组的起始位置
		iterator _finish;//指向容器中最后一个有效元素的下一个位置
		iterator _endofstorage;//指向容器已分配空间最后一个位置的下一个位置
	};
}

_finish - _start 即为 size（容器大小）,_endofstorage - _start 即为 capacity（容器容量是）。

模板声明和定义不能分离（.h 与 .cpp）。

二：默认成员函数

构造函数（move版本暂不实现）：

2.1 默认构造函数(default)

//1
vector()
	:_start(nullptr)
	,_finish(nullptr)
	,_endofstorage(nullptr)
{}
//2
vector()
{}
//成员函数要给上缺省值
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;

第二种我们是否可以直接不显式实现默认构造函数？而是让编译器自动生成？—当然可以，不过前提是没有其他构造函数的前提下。或者是：

// 强制编译器生成默认构造
vector() = default;

//不过成员函数要给上缺省值
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;

一旦有了其他的构造函数，编译器就不会再自动生成默认构造函数，用这种办法能够强制生成默认构造。

2.2 拷贝构造函数(copy)

//拷贝构造
vector(const vector<T>& v)
{
	reserve(v.capacity());
	for (auto& e : v)//相当于：T& e = *it(it是迭代器)
	{
		push_back(e);
	}
}

函数主要完成的是：先通过reserve(v.capacity)预先分配足够空间，再通过遍历原容器v，将v中的元素逐一复制到当前对象中。
关于使用(auto & e : v) 而非(auto e : v)：避免在遍历v容器时进行不必要的拷贝。

不加引用：每次迭代时，v中的元素都会拷贝到临时变量e中去（若T为自定义类型，调用T的拷贝构造）。加引用：e 直接绑定到v中的元素，无需进行拷贝，大大提升了效率。

reserve 与 push_back接下来会进行实现。

2.3 区域构造函数(range)

//区域构造函数
template<class InputIterator>//任意容器迭代器类型化
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

添加模板将任意迭代器类型化，这样就能够用各种类型的容器（如list，vector，string等）去构造函数。

代码测试：

2.4 初始化列表构造函数(initializer list)

1.初步了解一下 initializer_list 模板类

引入：std::initializer_list 是 C++11 引入的一个轻量级模板类，用于表示初始化列表（花括号 {} 包裹的值列表）。

要使用 initializer_list 首先要包含头文件<initializer_list>。
这种类型的对象由编译器从初始化列表声明中自动构造，而初始化列表声明是由一个大括号括起来，用逗号分隔元素的列表，il 就是一个initializer_list<int> 类型。
它类似于开一个数组如：int arr[] = { 10, 20 , 30}, 不过 il 对象里面存储的实际是两个指针，一个指向起始位置，一个指向末尾，其并非直接存储数组内容。

拥有三个接口：

我们可以用 typied(il).name 来获取 il 的类型名称进行验证。

2. 初始化列表构造函数

//初始化列表构造函数
vector(initializer_list<T> il)
{
	reserve(il.size());
	for (auto& e : il)
	{
		push_back(e);
	}
}

初始化列表构造函数的使用方式也不止一种，如下：

2.5 赋值重载函数

//交换
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> tmp)
{
	swap(tmp);
	return *this;
}

tmp是目标对象的拷贝，这里不能是引用，不能影响到目标对象。
*this 与 tmp 交换，通过交换内部指针（_start、_finish、_endofstorage），*this 接管了 tmp 的资源，而 tmp 接管了 this 的旧资源。即使this之前有资源，tmp会在函数结束时自动调用析构函数释放资源。
之后传引用返回 *this，避免拷贝。

2.6 析构函数

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

填充构造函数为了针对某些问题需要使用一些特殊的知识点，等掌握之后再来讲解。

二、普通成员函数

2.1 reserve

关于扩容，我们不能在原有空间的基础之上进行扩容，只能先去开辟一个新的更大的空间，之后将旧空间数据拷贝到新空间，然后释放旧空间。

开辟一个新的更大的空间。
将就空间数据拷贝到新的空间。
释放旧空间。

我们先来看一段代码，这段代码里面有两个错误，可以先试着找找看：

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

第一个错误：_finish = _start + size();

此size() 非我们所想的size() ,因为自_start = ptr 之后， _start 指向新的空间，而_finish仍指向之前的旧空间，进而导致 size() = _finish - _start 改变。我们可以把改变之前的 size()值用一个变量存起来，如 size_t old_size = size();

第二个错误：memcpy(ptr, _start, sizeof(T)* size());

**memcpy 进行的是一个浅拷贝（按字节复制），对于内置类型，这种复制是安全的。但对于自定义类型，就必须得进行深拷贝,否则它们会指向同一块内存空间（共享同一块资源），安全隐患大：

重复析构：多个对象的析构函数可能释放同一块内存
数据不一致：修改一个对象的资源会影响其他对象

我们可以使用之后的 push_back 来完成拷贝工作。修改之前：

代码中的变量ptr经过memcpy浅拷贝后指向的是_start所指向的空间，之后_start的空间被释放，ptr所指空间也被释放。

修改之后的代码：

void reserve(size_t n)
{
	//这里有一个坑，如果不事先储存一个旧的size值，之后的_finish算出来会是错的
	size_t old_size = size();
	if (n > capacity())
	{
		T* ptr = new T[n];
		//拷贝旧数据到新空间
		if (_start)
		{
			//memcpy(ptr, _start, sizeof(T) * old_size);
			for (int i = 0; i < old_size; i++)
			{
				ptr[i] = _start[i];
			}
			delete[] _start;
		}
		_start = ptr;
		_finish = _start + old_size;
		_endofstorage = _start + n;
	}
}

2.2 push_back

push_back等函数实现与顺序表类似，这里就不做过多解释了

void push_back(const T& x)
{
	if (_finish == _endofstorage)//检查容器是否已存满，存满则申请空间
	{
		//若容器容量为0，则固定分配4个sizeof(T)大小的空间，否则按照2倍扩容
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
	*_finish = x;
	_finish++;
}

2.3 pop_back

void pop_back()
{
	assert(!empty());//检查是否为空
	_finish--;
}
bool empty()
{
	return _finish == _start;
}

2.4 insert

1. 实现：

插入一个元素，需要把自pos及之后的元素从后往前一一往后移动一个位置，再再pos位置填上待插入元素即可。

检查是否需要扩容。
自pos位置的数据都往后移动一个位置。
pos 位置填上待插入数据，_finish++。

代码如下：

iterator& insert(iterator pos, const T& x)
{
	//检查是否越界
	assert(pos >= _start);
	assert(pos <= _finish);

	if (_finish == _endofstorage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		//更新一下pos
		pos = _start + len;
	}
	iterator end = _finish - 1;

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

关于更新 pos：

若需要扩容，经过reserve处理后，_start等迭代器都指向了新的空间，但是pos不会被处理，我们需要进行更新操作->需要实现存储一下pos到_start所隔元素个数即len。

2.迭代器失效

概念：在 C++ 中，迭代器失效是使用动态容器（如vector、list、map等）时的常见问题。当容器的结构被修改（如插入、删除元素）后，原来指向容器元素的迭代器可能不再有效，继续使用这些迭代器会导致未定义行为（如程序崩溃、数据错误），类似于野指针。

我们来看下一段关于insert的测试代码：

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
Print(v);

int x;
cin >> x;
auto it = find(v.begin(), v.end(), x);
v.insert(it, 9);

这里的it 能否被继续使用？不能。

it 跟上面需要更新pos的问题一样，初始给予的是4个sizeof(int)大小的空间（空间已满），插入一个值需要进行扩容创建新的空间，reserve处理之后 it 指向的是已经销毁的旧空间，而非新空间。it失效。
由于c++标准里并没有规定vector扩容规则，所以对于一段陌生代码我们不知道什么时候会扩容，统一认为 insert 以后，it 迭代器失效。

若要继续使用 it ，需要为其赋值一个其他的有效迭代器，如用 insert 的返回值进行赋值更新。it = v.insert(it, 9)

2.5 erase

需要将自pos及之后的元素从前往后都向前移动一个位置，_finish–。

iterator& erase(iterator pos)
{
	//检查pos是否合理
	assert(pos >= _start);
	assert(pos < _finish);
	//挪动数据
	iterator it = pos + 1;

	while (it != _finish)
	{
		*(it - 1) = *it;
		it++;
	}
	_finish--;
	return pos;
}

传值给pos的迭代器自erase之后会失效，对于不重新赋值的迭代器的再次使用，不同的编译器处理的方式不同，vs里面会出现断言终止程序，而gcc默认不对迭代器进行安全检查。
解决方法也是给传值给pos的迭代器赋予新的有效迭代器值，比如erase的返回值。

2.6 clear

即为size() = 0时–>_finish == _start。

void clear()
{
	_finish = _start;
}

2.7 resize

void resize(size_type count, const value_type& value = value_type());

resize的基本功能：

若 count > size(), 在结尾追加元素。
若 count < size(), 删除尾部元素。

void resize(size_t n, const T& val = T())
{
	//若n小于size,需要进行截断操作
	if (n < size())
	{
		_finish = _start + n;
	}
	//否则进行追加元素操作
	else
	{
		reserve(n);
		while (_finish != _start + n)
		{
			*_finish = x;
			_finish++;
		}
	}
}

关于 const T& val = T()：c++规定，T()，若T为自定义类型，则会调用默认构造函数，若为内置类型，则会进行零初始化，将值设置为0 或 nullptr。

补充：C++ 中引用形参的缺省值规则 引用形参的缺省值必须是：

全局变量或静态变量。
具有静态存储期的对象。
通过函数返回的引用。

但 const 引用可以绑定到临时对象，因此允许使用字面量作为缺省值–>用引用形参尽量都加上const。

2.8 operator[]

//可修改
T& operator[](size_t i)
{
	assert(i < size());
	return _start[i];
}
//不可修改，遇到const修饰的vector类型调用
const T& operator[](size_t i)const
{
	assert(i < size());
	return _start[i];
}