跳到主要内容 STL vector 常用接口使用及底层原理与实现 | 极客日志
C++ 算法
STL vector 常用接口使用及底层原理与实现 STL vector 是 C++ 标准模板库中常用的动态数组容器。 vector 的构造方式、常用接口如 push_back、pop_back、insert、erase 等的使用，以及 size、capacity、reserve、resize 等空间管理函数的区别。重点讲解了迭代器的概念及其失效场景，包括扩容、插入删除等操作导致的迭代器失效问题。此外，文章还深入剖析了 vector 的底层内存结构，通过模拟实现展示了连续内存空间的分配与管理机制，帮助读者理解其性能特点及注意事项。
墨染流年 发布于 2026/3/15 更新于 2026/4/18 1. vector 的介绍及使用
1.1 vector 的介绍
vector 的文档介绍：https://cplusplus.com/reference/vector/vector/
1.2 vector 的使用
1.2.1 vector 的构造
构造函数 功能 vector()（重点） 无参构造 vector(size_type n, const value_type& val = value_type()) 构造并初始化 n 个 val vector(const vector& x)（重点） 拷贝构造 vector(InputIterator first, InputIterator last) 使用迭代器进行初始化构造 (可以用于其他容器构造 vector)
1.2.2 vector iterator 的使用
接口 功能 begin()+end() begin() 获取第一个数据位置的 iterator/const_iterator，end() 获取最后一个数据的下一个位置的 iterator/const_iterator rbegin()+rend() rbegin() 获取最后一个数据位置的 reverse_iterator，rend() 获取第一个数据前一个位置的 reverse_iterator
1.2.3 vector 的空间增长问题
size() 函数，获取数据个数
函数原型：size_type size() const;
capacity() 函数，获取容量大小
函数原型：size_type capacity() const;
empty() 函数，判空，空返回 true，否则返回 false
函数原型：bool empty() const;
resize() 函数
函数原型：void resize(size_type n, value_type val = value_type());
如果 n < size() 会保留前 n 个元素删除其他多余的元素。
如果 n > size() 则会插入元素使 size() 达到 n 个，若指定 val 就会填充 val。
如果 n > capacity() 则会重新分配空间使 size()=capacity()=n。
reserve() 函数
函数原型：void reserve(size_type n);
如果 n < capacity() 什么都不变。
如果 n > capacity()，则会重新分配空间使 capacity()=n。
注：capacity 的代码在 vs 和 g++ 下分别运行会发现，vs 下 capacity 是按 1.5 倍增长的，g++ 是按 2 倍增长的。这个问题经常会考察，不要固化的认为，vector 增容都是 2 倍，具体增长多少是根据具体需求定义的。vs 是 PJ 版本 STL，g++ 是 SGI 版本 STL。
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
reserve 只负责开辟空间，如果确定知道需要用多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。
resize 在开空间的同时还会进行初始化，影响 size。
void TestVectorExpand () size_t sz;
std::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' ;
}
}
}
1.2.4 vector 增删查改
push_back()，尾插
函数原型：void push_back(const value_type& val);
pop_back()，尾删
函数原型：void pop_back();
find()（注意这个是算法模块实现，不是 vector 的成员接口），查找
函数原型：InputIterator find(InputIterator first, InputIterator last, const T& val);
使用时使用迭代器传一个区间和要查找的值，区间左闭右开 [first,last)，若区间有要查找的值则返回值所在的迭代器，若没有则返回 last。
insert() 插入
函数原型：iterator insert(iterator position, const value_type& val); void insert(iterator position, size_type n, const value_type& val); void insert(iterator position, InputIterator first, InputIterator last);
在 position 位置前插入 val；
在 position 位置前插入 n 个 val;
在 position 位置前插入一个区间的值，区间左闭右开；
insert() 插入改变 size() 大小，同时如果插入数量多余 capacity() 剩余空间就会分配新空间这会导致迭代器失效，同时因为 vector 底层是数组所以插入需要每个数据后移代码效率较低。
erase() 删除
函数原型：iterator erase(iterator position); iterator erase(iterator first, iterator last);
删除 position 位置的元素。
删除一个区间的元素，区间左开右闭。
erase 改变 size() 大小，同时删除后的元素需要前移，迭代器失效同时效率较低。
swap() 交换
函数原型：template <class T, class Alloc> void swap(vector<T,Alloc>& x, vector<T,Alloc>& y);
容器 x 的内容与 y 容器的内容物交换。两个容器对象必须具有相同类型（相同的模板参数），尽管大小可能不同。与算法中实现的 swap 效果相同。
#include <iostream>
#include <vector>
int main () unsigned int i;
std::vector<int > foo (3 , 100 ) ;
std::vector<int > bar (5 , 200 ) ;
foo.swap (bar);
std::cout << "foo contains:" ;
for (std::vector<int >::iterator it = foo.begin (); it != foo.end (); ++it)
std::cout << ' ' << *it;
std::cout << '\n' ;
std::cout << "bar contains:" ;
for (std::vector<int >::iterator it = bar.begin (); it != bar.end (); ++it)
std::cout << ' ' << *it;
std::cout << '\n' ;
return 0 ;
}
operator[]
函数原型：reference operator[](size_type n); const_reference operator[](size_type n) const;
返回向量容器中位置 n 的元素的引用。一个类似的成员函数 vector::at 与该算符函数行为相同，但 vector::at 是边界检查的，通过抛出 out_of_range 异常来表示请求位置超出范围。所以要注意 n 不要超过边界。
1.2.5 vector 迭代器失效问题。（重点） 迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃 (即如果继续使用已经失效的迭代器，程序可能会崩溃)。
1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back 等。
#include <iostream>
using namespace std;
#include <vector>
int main () int > v{1 , 2 , 3 , 4 , 5 , 6 };
auto it = v.begin ();
v.resize (100 , 8 );
v.reserve (100 );
v.insert (v.begin (), 0 );
v.push_back (8 );
v.assign (100 , 8 );
while (it != v.end ()) {
cout << *it << " " ;
++it;
}
cout << endl;
return 0 ;
}
#include <iostream>
using namespace std;
#include <vector>
int main () int a[] = {1 , 2 , 3 , 4 };
vector<int > v (a, a + sizeof (a) / sizeof (int )) ;
vector<int >::iterator pos = find (v.begin (), v.end (), 3 );
v.erase (pos);
cout << *pos << endl;
return 0 ;
}
erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 就失效了。因此删除 vector 中任意位置上元素时，vs 就认为该位置迭代器失效了。
3. 与 vector 类似，string 在插入 + 扩容操作+erase 之后，迭代器也会失效
#include <string>
void TestString () string s ("hello" ) ;
auto it = s.begin ();
while (it != s.end ()) {
cout << *it;
++it;
}
cout << endl;
it = s.begin ();
while (it != s.end ()) {
it = s.erase (it);
}
}
2. vector 深度剖析及模拟实现 #pragma once
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <string>
using namespace std;
class MyVector {
public :
typedef T* iterator;
typedef const T* const_iterator;
MyVector () = default ;
MyVector (const MyVector<T>& v) {
reserve (v.size ());
for (int i = 0 ; i < v.size (); i++) {
push_back (v[i]);
}
}
MyVector<T>& operator =(MyVector<T> v) {
swap (v);
return *this ;
}
void swap (MyVector<T>& v) swap (_start, v._start);
std::swap (_finish, v._finish);
std::swap (_end_of, v._end_of);
}
template <class inputIterator>
MyVector (inputIterator first, inputIterator last) while (first != last) {
push_back (*first);
first++;
}
}
MyVector (size_t n, const T& val = T ()) {
reserve (n);
for (int i = 0 ; i < n; i++) {
push_back (val);
}
}
~MyVector () {
if (_start) {
delete [] _start;
_start = _finish = _end_of = nullptr ;
}
}
iterator begin () {
return _start;
}
iterator end () {
return _finish;
}
T& operator [](size_t n) {
return *(_start + n);
}
const T& operator [](size_t i) const {
assert (i < size ());
return _start[i];
}
bool empty () return _start == _finish;
}
void reserve (size_t n) if (n > capacity ()) {
size_t old_size = size ();
T* tmp = new T[n];
for (int i = 0 ; i < size (); i++) {
tmp[i] = _start[i];
}
delete [] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of = tmp + n;
}
}
void resize (size_t n, T val = T()) if (n < size ()) {
_finish = _start + n;
} else {
while (_finish < _start + n) {
*_finish = val;
++_finish;
}
}
}
void push_back (const T& val) if (_finish == _end_of) {
reserve (capacity () == 0 ? 4 : capacity () * 2 );
}
*_finish = val;
_finish++;
}
void pop_back () assert (!empty ());
_finish--;
}
iterator insert (iterator pos, const T& x) {
assert (pos >= _start && pos <= _finish);
if (_finish == _end_of) {
size_t n = pos - _start;
reserve (capacity () == 0 ? 4 : capacity () * 2 );
pos = _start + n;
}
int i = 0 ;
while (pos + i < _finish) {
*(_finish - i - 1 ) = *(_finish - i);
i++;
}
*pos = x;
_finish++;
return pos;
}
void erase (iterator pos) assert (!empty ());
assert (pos >= _start && pos <= _finish);
int i = 0 ;
while (pos + i < _finish) {
*(pos + i) = *(pos + 1 + i);
i++;
}
_finish--;
}
T* data () {
return _start;
}
int size () const return _finish - _start;
}
int capacity () return _end_of - _start;
}
private :
T* _start = nullptr ;
T* _finish = nullptr ;
T* _end_of = nullptr ;
};
template <class T>
void print_T (T& val) for (auto & e : val) {
cout << e << " " ;
}
cout << endl;
}
void test_vector1 () int > v;
v.push_back (1 );
v.push_back (2 );
v.push_back (3 );
v.push_back (4 );
v.push_back (5 );
for (size_t i = 0 ; i < v.size (); i++) {
cout << v[i] << " " ;
}
cout << endl;
MyVector<int >::iterator it = v.begin ();
while (it != v.end ()) {
cout << *it << " " ;
++it;
}
cout << endl;
for (auto e : v) {
cout << e << " " ;
}
cout << endl;
print_T (v);
MyVector<double > vd;
vd.push_back (1.1 );
vd.push_back (2.1 );
vd.push_back (3.1 );
vd.push_back (4.1 );
vd.push_back (5.1 );
print_T (vd);
}
void test_vector2 () int > v;
v.push_back (1 );
v.push_back (2 );
v.push_back (3 );
v.push_back (4 );
v.push_back (5 );
print_T (v);
int x;
cin >> x;
auto p = find (v.begin (), v.end (), x);
if (p != v.end ()) {
p = v.insert (p, 40 );
(*(p + 1 )) *= 10 ;
}
print_T (v);
}
void test_vector3 () int > v;
v.push_back (1 );
v.push_back (2 );
v.push_back (3 );
v.push_back (4 );
print_T (v);
auto it = v.begin ();
while (it != v.end ()) {
if (*it % 2 == 0 ) {
it = v.erase (it);
} else {
++it;
}
}
print_T (v);
v.reserve (20 );
print_T (v);
}
void test_vector4 () int i = 0 ;
int j = 1 ;
int k (2 ) int > v;
v.resize (10 , 1 );
print_T (v);
v.reserve (20 );
print_T (v);
cout << v.size () << endl;
cout << v.capacity () << endl;
v.resize (15 , 2 );
print_T (v);
v.resize (25 , 3 );
print_T (v);
v.resize (5 );
print_T (v);
}
void test_vector5 () int > v1;
v1. push_back (1 );
v1. push_back (2 );
v1. push_back (3 );
v1. push_back (4 );
print_T (v1);
MyVector<int > v2 = v1;
print_T (v2);
MyVector<int > v3;
v3. push_back (10 );
v3. push_back (20 );
v3. push_back (30 );
v1 = v3;
print_T (v1);
print_T (v3);
}
void test_vector6 () int > v1;
v1. push_back (1 );
v1. push_back (2 );
v1. push_back (3 );
v1. push_back (4 );
v1. push_back (4 );
v1. push_back (4 );
list<int > lt;
lt.push_back (10 );
lt.push_back (10 );
lt.push_back (10 );
lt.push_back (10 );
print_T (lt);
MyVector<string> v4 (10 , "1111111" ) ;
print_T (v4);
MyVector<int > v5 (10 ) ;
print_T (v5);
MyVector<int > v6 (10u , 1 ) ;
print_T (v6);
MyVector<int > v7 (10 , 1 ) ;
print_T (v7);
}
void test_vector7 () push_back ("11111111111111111111" );
v.push_back ("11111111111111111111" );
v.push_back ("11111111111111111111" );
v.push_back ("11111111111111111111" );
print_T (v);
v.push_back ("11111111111111111111" );
print_T (v);
}
2.2 动态二维数组理解
void test2vector (size_t n) int >> vv (n);
for (size_t i = 0 ; i < n; ++i) vv[i].resize (i + 1 , 1 );
for (int i = 2 ; i < n; i++) {
for (int j = 1 ; j < i; j++) {
vv[i][j] = vv[i - 1 ][j] + vv[i - 1 ][j - 1 ];
}
}
}
std::vector<std::vector<int>> vv(n) 构造一个 vv 动态二维数组，vv 中总共有 n 个元素，每个元素都是 vector 类型的，每行没有包含任何元素，如果 n 为 5 时如下所示：
