C++ vector

比昨天多敲两行

428人浏览 · 2026-03-17 10:15:47

比昨天多敲两行 · 2026-03-17 10:15:47 发布

vector的介绍及使用

一、vector 核心认知：动态数组的本质

vector 本质是动态连续存储的容器，底层基于数组实现，具备以下核心特点：

支持随机访问（[]/at()），时间复杂度 O (1)；
尾部插入 / 删除（push_back()/pop_back()）效率高，平均 O (1)；
中间 / 头部插入 / 删除效率低（需移动元素），时间复杂度 O (n)；
动态扩容：当存储空间不足时，自动申请更大的内存（通常是原容量的 2 倍），拷贝原数据后释放旧内存。

二、vector 与 string 的底层关联：同源的动态容器

vector 和 string 是 STL 中最核心的两个动态容器，底层设计高度相似，甚至可以说string是 “特殊的 vector<char>”，二者的关联与差异可总结为以下几点：

1. 核心共性（底层逻辑一致）

共性维度	具体说明
存储结构	均基于连续内存（数组）实现，支持随机访问。
扩容机制	容量不足时均触发 “新内存申请→数据拷贝→旧内存释放”，扩容倍数通常为 2 倍。
核心方法	均提供`size()`/`capacity()`/`reserve()`/`resize()`/`empty()`等方法，语义完全一致。
迭代器类型	均支持随机访问迭代器（`random_access_iterator`），可使用`begin()`/`end()`遍历。

2. 关键差异（string 的字符专属特性）

对比维度	vector<T>	string
元素类型	通用型，支持任意类型（int / 自定义类等）。	专属型，仅存储 char 类型，适配 C 风格字符串。
结束符处理	无结束符概念，元素就是实际存储内容。	自动维护`\0`结束符（不计入 size），兼容`c_str()`/`data()`接口。
专属方法	无字符相关方法。	提供`find()`/`substr()`/`append()`/`compare()`等字符串操作方法。
resize 默认填充值	用元素类型默认值（如 int 填 0，自定义类调用默认构造）。	无填充参数时默认填`\0`，保证字符串合法性。

更多关于vector的使用：vector文档的介绍

三、vector的使用

vector学习时一定要学会查看文档： vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，一些函数的使用和功能与string差不多，就不一一展示。下面列出一些与string有点区别的函数和特性。

构造函数声明	接口说明
vector()（重点）	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x); （重点）	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

vector iterator 的使用

iterator的使用	接口说明
begin + end（重点）	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

void test_vector1()
{
	vector<int> v1;//空表
	vector<int> v2(10,1);//10个1
	vector<int> v3(++v2.begin(), --v2.end());//迭代器区间初始化

	//vector支持迭代器遍历
	for (size_t i = 0; i < v3.size(); i++)
	{
		cout << v3[i] << " ";
	}
	cout << endl;

	vector<int>::iterator it = v3.begin();
	while (it != v3.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

v1,v2,v3的初始化情况：

vector capacity空间增长问题

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize(重点)	改变vector的size
reserve（重点）	改变vector的capacity

vector的capacity与string的capacity有点不同。

下面是一串测试vector的capacity在不同环境下空间增长的代码：

void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

结果：

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2 倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

vector reserve：

如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够，用reserve。

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

string的reserve（这里在vs22平台下测试）和vector的reserve的区别：

vector的reserve在vs2022版本下不缩容，在g++平台也不缩容。

string的reserve在vs2022版本下不缩容，在g++平台会缩容。

vector：：reserve测试结果：

共性：两者都只修改 capacity()（预分配空间），不修改 size()（实际元素 / 字符数），也不构造 / 初始化新元素；
本质差异根源：string 是字符专用容器，需兼容 C 风格字符串的 \0 结束符，因此内存分配会多 1 字节；而 vector 是通用容器，无特殊结束符要求，仅按元素数量分配内存。

vector resize：

维度	具体说明
核心目标	直接修改 `vector` 的 `size()`（实际存储的元素数量），强制将有效元素数设置为指定值 `n`。
参数格式	两种形式：1. `resize(n)`：仅指定目标元素数，补充元素用默认值；2. `resize(n, val)`：指定目标元素数 + 补充元素的填充值。
当 `n < 当前size()`	截断操作：1. 保留前 `n` 个元素，删除从索引 `n` 开始的所有后续元素；2. `size()` 变为 `n`，`capacity()` 保持不变（不会收缩）；3. 无内存重新分配，仅销毁多余元素。
当 `n == 当前size()`	无任何操作：`size()`、`capacity()`、元素内容均保持不变。
当 `n > 当前size()`	扩容补充操作：1. 若 `n ≤ 当前capacity()`：直接在末尾补充 `n - size()` 个元素，无需重新分配内存；2. 若 `n > 当前capacity()`：先触发扩容（重新分配更大内存、拷贝旧元素），再补充元素；3. 补充的元素值： - 无 `val` 时：用元素类型的默认构造值（如 `int` 填 `0`、`string` 填空串、自定义类调用默认构造）； - 有 `val` 时：用指定的 `val` 填充。
对 `capacity()` 的影响	仅在 `n > 当前capacity()` 时，`capacity()` 会增大（扩容后通常为原容量的 2 倍或更大）；其他情况 `capacity()` 完全不变（即使截断也不收缩）。
典型使用场景	1. 提前设定 `vector` 的元素数量，避免频繁追加元素触发扩容；2. 截断多余元素，精简有效数据；3. 统一初始化 `vector` 到指定长度并填充默认值。

void test_vector3()
{
	vector<int> v(10, 1);
	v.reserve(20);
	cout << v.size() << endl;//10
	cout << v.capacity() << endl;//20

	v.resize(15,2);//补齐15个数据,缺5个用2填充
	cout << v.size() << endl;//15
	cout << v.capacity() << endl;//20

	v.resize(25,3);
	cout << v.size() << endl;//25
	cout << v.capacity() << endl;//20<25,capacity按1.5倍扩到30

	v.resize(5);//size缩到只剩5个1，capacity还是30
	cout << v.size() << endl;//5
	cout << v.capacity() << endl;//30
}

vector的resize在开空间的同时还会进行初始化，影响size。

vector insrt:

不支持下标访问，只支持迭代器访问。

void test_vector4()
{
	vector<int> v(10, 1);
	v.push_back(2);//尾插一个2
	//迭代器遍历：
	v.insert(v.begin(), 0);//头插一个0
	for (auto e : v)
	{
		cout << e << " ";//0 1 1 1 1 1 1 1 1 1 1 2
	}
	cout << endl;

	v.insert(v.begin() + 3, 10);//第3个位置插入一个10 c 
	for (auto e : v)
	{
		cout << e << " ";//0 1 1 10 1 1 1 1 1 1 1 1 2
	}
	cout << endl;
}

vector不支持流插入和流提取。

vector和string最大的区别就是vector没有\0。

vector里不仅能存int，double，char，还能存stirng和vector。

示例：

void test_vector5()
{
	vector<string> v1;//vector里存string
	string s1("xxxxx");
	v1.push_back(s1);//以前的写法

	v1.push_back("yyyyy");//隐式类型转换

	
	for (const auto& e : v1)//这里v1的string要走拷贝构造代价比较大，所以加&，如果不改变就加多一个const
	{                       //以前是int型，拷贝代价不大就没加&		
		cout << e << " ";
	}
	cout << endl;

	vector<int> v2(5, 1);
	vector<vector<int>> vv(10,v2);//vector里存vector就是二维数组
	vv[1][2] = 5;//这样可以修改或访问数据

}

图解：

四、迭代器失效问题（重点）

迭代器失效是 vector 使用中最高频的错误，本质是迭代器指向的内存地址失效（内存释放 / 元素移动），访问失效迭代器会导致未定义行为（崩溃 / 数据错乱）。以下梳理迭代器失效的核心场景及解决方案。

1. 迭代器失效的核心场景

场景 1：扩容导致的迭代器失效（最常见）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1,2,3};
    vec.reserve(3); // 手动设置capacity=3，确保后续push_back触发扩容
    vector<int>::iterator it = vec.begin(); // 迭代器指向第一个元素

    vec.push_back(4); // 触发扩容，原内存释放，it失效
    cout << *it << endl; // 未定义行为：可能崩溃/输出随机值
    return 0;
}

解决方案：扩容后重新获取迭代器

vec.push_back(4);
it = vec.begin(); // 重新绑定迭代器
cout << *it << endl; // 正确输出：1

场景 2：插入 / 删除元素导致的迭代器失效

插入元素：插入位置后的所有迭代器失效（元素后移，地址变化）；若触发扩容，所有迭代器失效。
删除元素：删除位置后的所有迭代器失效（元素前移）；erase()返回新的有效迭代器。

错误示例：

vector<int> vec = {10,20,30,40};
vector<int>::iterator it = vec.begin() + 1; // 指向20

// 插入元素：it及后续迭代器失效
vec.insert(it, 15);
cout << *it << endl; // 失效迭代器，未定义行为

// 删除元素：it失效
vec.erase(vec.begin() + 2);
cout << *it << endl; // 失效迭代器，未定义行为

解决方案：利用 insert/erase 的返回值更新迭代器。

场景 3：清空 / 重置容器导致的迭代器失效

错误示例：

vector<int> vec = {1,2,3};
vector<int>::iterator it = vec.begin();
vec.clear(); // 清空元素，it失效
cout << *it << endl; // 未定义行为（野指针）

解决方案：清空后重新获取迭代器（若需继续使用）

vec.clear();
it = vec.begin(); // it指向end()，空容器迭代器不可解引用，但可用于判断
if (it == vec.end()) cout << "迭代器指向空容器末尾" << endl; // 正确

2. 迭代器失效的通用避坑原则：

扩容后必重新绑定迭代器：涉及push_back()/insert()等可能扩容的操作后，不要复用之前的迭代器；
利用返回值更新迭代器：insert()/erase()返回的迭代器是唯一可靠的新迭代器；
遍历中修改容器需谨慎：遍历 vector 时若要插入 / 删除元素，优先用返回值更新迭代器，而非直接复用；
避免存储迭代器长期使用：迭代器仅适合短期使用（如单次遍历），不建议作为成员变量长期存储。

五、性能优化建议

预分配空间：如果知道大概的元素数量，使用reserve()避免多次扩容
使用emplace_back：C++11引入，避免不必要的拷贝/移动
避免在循环中判断容量：在循环前确保容量足够
使用swap释放内存：vector<T>().swap(v)可以真正释放内存

vector<int> v;
v.reserve(1000);  // 预分配空间，避免push_back时多次扩容
 
for (int i = 0; i < 1000; ++i) {
    v.push_back(i);  // 不会触发扩容
}
 
// 释放内存
vector<int>().swap(v);  // v现在为空，且capacity为0

模拟实现vector

模拟实现vector我们按照库里面用三个指针来表示顺序表里的位置关系（本质和size，capacity是一样的）：

start：初始位置；

finish：有效数据位置；

end_of_storage:最大空间位置。

这三个指针与之前string的size和capacity接口的位置关系：

只实现一些常用或者重要的函数，例如final函数vector是调用库里面的，就不实现了。

1.基础的vector：

vector.h:

#include<iostream>
#include<assert.h>
using namespace std;
namespace zwg
{
	template<class T>
	class vector
	{
	public:
		//一些函数要用到迭代区间进行操作
        //模拟实现迭代器和const迭代器
		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;
		}
	//构造函数
	/*vector()//这样写也可以
	{}*/
	vector() = default;// C++11 强制生成默认构造
	
	//拷贝构造
	vector(const vector<T>& v)
	{
		reserve(v.size());//提前开好空间
		for (auto& e : v)
		{
			push_back(e);
		}
	}

    //清除数据
    void clear()
    {
	_finish = _start;
    }

	//析构函数
	~vector()
	{
		if (_start)
		{
			delete[] _start;//因为这三个指针指向同一块空间，释放一个就行
			_start = _finish = _end_of_storage = nullptr;//全部置空
		}
	}
size_t size()const
{
	return _finish - _start;
}
size_t capacity()const
{
	return _end_of_storage - _start;
}
//重载[]
T& operator[](size_t n)
{
	assert(n < size());
	return _start[n];
}

const T& operator[](size_t n)const
{
	assert(n < size());
	return _start[n];
}
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;
};
//vector的输出
template<class T>
void print_container(const vector<T>& v)
{
	// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator
	// 是类型还是静态成员变量，这里必须用 typename 明确 “这是类型”
	typename vector<T>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

2.vector的插入/删除：

namespace zwg
{
   //尾删一个元素
   void pop_back()
  {
	assert(!empty());
	return --_finish;
  }

   //尾插
void push_back(const T& n)
{
	if (_finish==_end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity()*2);
	}
	*_finish = n;
	++_finish;
}

//迭代区间删除一个元素
void erase(iterator pos)
{
	assert(pos > _start);
	assert(pos <= _finish);
	iterator it = pos + 1;
	while (it != end())
	{
		*(it - 1) = *it;//用到了重载的=
		++it;
	}
	--_finish;
}

//迭代区间插入
iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	//扩容
	if (_finish == _end_of_storage)
	{
		int len = pos - _start;//记住pos位置，防止扩容后pos位置丢失（迭代器失效问题：野指针）
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	iterator end = _finish - 1;
	while (end>=pos) 
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;
	++_finish;
	return pos;
}
}

3.vector的赋值重载：

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

4.vector的迭代区间构造：

namespace zwg
{
  //迭代器区间构造
  //类模板的成员函数还可以继续是函数模板
  template <class inputiterator>
  vector(inputiterator first, inputiterator last)
  {
	while (first != last)//这里可以用<，但是为了支持更多容器（例如链表），还是使用！=靠谱一些
	{
		push_back(*first);
		++first;
	}
  }
}

5.vector的n个val值初始化：

namespace zwg
{
	//n个val初始化
	vector(int n, const T& val = T())
	{
		reserve(n);
		for (int i = 0; i < n; i++)
		{
			push_back(val);
		}
	}
}

6.verctor的reserve：

namespace zwg
{
  //预开辟空间
  void reserve(size_t n)
  {
	if (n > capacity())
	{
		size_t old_size = size();//记录size位置
		T* tmp = new T[capacity() + n];				
		//memcpy(tmp, _start, sizeof(T) * old_size);//浅拷贝会有问题
		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;
	}
  }
}

7.vector的resize：

namespace zwg
{
  //用n个数据初始化
  void resize(size_t n, T val = T())
  {
	if (n <size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish < _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
  }
}

整体实现

vector.h：

#pragma once
#include<iostream>
#include<assert.h>

using namespace std;
namespace zwg
{
	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;
		}
		
		//构造函数
		/*vector()//这样写也可以
		{}*/
		vector() = default;// C++11 强制生成默认构造
		
		//拷贝构造
		vector(const vector<T>& v)
		{
			reserve(v.size());//提前开好空间
			for (auto& e : v)
			{
				push_back(e);
			}
		}
		//清除数据
		void clear()
		{
			_finish = _start;
		}
		//析构函数
		~vector()
		{
			if (_start)
			{
				delete[] _start;//因为这三个指针指向同一块空间，释放一个就行
				_start = _finish = _end_of_storage = nullptr;//全部置空
			}
		}
		//尾删一个元素
		void pop_back()
		{
			assert(!empty());
			return --_finish;
		}

		size_t size()const
		{
			return _finish - _start;
		}
		size_t capacity()const
		{
			return _end_of_storage - _start;
		}
		//判空
		bool empty()
		{
			return _start == _finish;
		}
		//尾插
		void push_back(const T& n)
		{
			if (_finish==_end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity()*2);
			}
			*_finish = n;
			++_finish;
		}
		//迭代区间删除一个元素
		void erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			iterator it = pos + 1;
			while (it != end())
			{
				*(it - 1) = *it;//用到了重载的=
				++it;
			}
			--_finish;
		}
		//迭代区间插入
		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			//扩容
			if (_finish == _end_of_storage)
			{
				int len = pos - _start;//记住pos位置，防止扩容后pos位置丢失（迭代器失效问题：野指针）
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end>=pos) 
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
			return pos;
		}

		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;
		}
		//迭代器区间构造
		//类模板的成员函数还可以继续是函数模板	
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)//这里可以用<，但是为了支持更多容器（例如链表），还是使用！=靠谱一些
			{
				push_back(*first);
				++first;
			}
		}
		//n个val初始化
		vector(int n, const T& val = T())
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		//重载[]
		T& operator[](size_t n)
		{
			assert(n < size());
			return _start[n];
		}

		const T& operator[](size_t n)const
		{
			assert(n < size());
			return _start[n];
		}
		//预开辟空间
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t old_size = size();
				T* tmp = new T[capacity() + n];				
				//memcpy(tmp, _start, sizeof(T) * old_size);//浅拷贝会有问题
				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;
			}
		}
		//用n个数据初始化
		void resize(size_t n, T val = T())
		{
			if (n <size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}


	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
	//vector的输出
	template<class T>
	void print_container(const vector<T>& v)
	{
		// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator
		// 是类型还是静态成员变量
		typename vector<T>::const_iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}