C++ vector 容器基于动态数组实现，通过三个指针管理内存。解析了 vector 的构造函数、赋值运算符、容量操作及元素访问修改操作。重点阐述了迭代器失效问题：扩容时所有迭代器失效，erase 后删除位置及后续迭代器失效，需使用 erase 返回值更新迭代器。提供了完整的 vector 模拟实现代码，涵盖命名空间 bit 下的类定义及测试用例，展示了现代 C++ 写法如 swap 交换资源及异常安全机制。
在 C++ 中，模板是实现泛型编程的重要工具，它允许我们编写与数据类型无关的代码。vector 容器正是通过模板技术实现的，可以存储任意类型的数据：
template<class T> class vector { // ... 实现细节 };
这里的 T 是类型参数，当我们创建 vector 对象时，需要指定具体的类型
vector<int> intVector; // 存储 int 类型的 vector
vector<string> strVector; // 存储 string 类型的 vector
vector<double> dblVector; // 存储 double 类型的 vector
模板的使用让 vector 具有了极强的通用性，可以容纳各种数据类型，从基本类型到自定义类类型。
vector 底层使用动态数组实现，通过三个指针来管理内存：
private:
iterator _start = nullptr; // 指向数组的开始位置
iterator _finish = nullptr; // 指向最后一个元素的下一个位置
iterator _end_of_storage = nullptr; // 指向分配内存的末尾
在这里，给了三个指针缺省值 nullptr 初始化。
vector 提供了多种构造函数来满足不同的初始化需求：
vector(size_t n, const T& val = T()) {
reserve(n);
for (size_t i = 0; i < n; i++) {
push_back(val);
}
}
使用示例：
vector<int> v1(5); // 包含 5 个 0 的 vector
vector<int> v2(3, 10); // 包含 3 个 10 的 vector
vector<string> v3(2, "hello"); // 包含 2 个"hello"的 vector
template <class InputIterator>
vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first);
++first;
}
}
这个构造函数是函数模板，可以接受任意类型的迭代器：
int arr[] = {1, 2, 3, 4, 5};
vector<int> v1(arr, arr + 5); // 从数组构造
vector<int> v2(v1.begin(), v1.end()); // 从另一个 vector 构造
vector(const vector<T>& v) {
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
现代写法通过创建临时对象并交换资源，代码简洁且异常安全。
vector<T>& operator=(vector<T> tmp) {
swap(tmp);
return *this;
}
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
if (_start) {
for (size_t i = 0; i < sz; i++) {
std::swap(tmp[i], _start[i]);
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
std::swap 而不是直接赋值，这样可以高效地交换资源。memcpy，对于管理资源的类（如 string）会导致浅拷贝问题！_finish 和 _end_of_storage 指针void resize(size_t n, T val = T()) {
if (n < size()) {
// 缩小 size，只是移动_finish 指针
_finish = _start + n;
} else {
reserve(n); // 可能需要扩容
while (_finish < _start + n) {
*_finish = val;
++_finish;
}
}
}
这里使用匿名对象做缺省参数。
使用示例：
vector<int> v = {1, 2, 3};
v.resize(5); // 变为 {1, 2, 3, 0, 0}
v.resize(2); // 变为 {1, 2}
size_t capacity() const { return _end_of_storage - _start; }
size_t size() const { return _finish - _start; }
T& operator[](size_t i) {
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const {
assert(i < size());
return _start[i];
}
提供 const 和非 const 版本，支持读写访问和只读访问。
void push_back(const T& x) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
扩容策略：初始为 0 时分配 4 个元素空间，否则每次扩容为原来的 2 倍。
void pop_back() {
assert(!empty());
--_finish;
}
iterator insert(iterator pos, const T& x) {
assert(pos >= _start);
assert(pos <= _finish);
// 扩容
if (_finish == _end_of_storage) {
size_t len = pos - _start;
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;
}
扩容后需要重新计算 pos 的位置，因为_start 可能改变了。
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
迭代器失效是使用 vector 时需要特别注意的问题，不当使用会导致未定义行为。
当在 vector 中插入元素时，如果引起扩容，所有迭代器都会失效。
void test_vector2() {
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto it = v.begin() + 3;
v.insert(v.begin(), 0); // 可能引起扩容
// insert 以后，it 失效了，不能再使用
// *it = 10; // 错误！未定义行为
}
erase 操作会使被删除元素及其后面所有元素的迭代器失效。
void test_vector3() {
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto it = v.begin() + 2;
v.erase(v.begin()); // 删除第一个元素
// it 失效了，不能访问，访问结果未定义
// cout << *it << endl; // 错误！
}
正确使用 erase 删除元素的模式：
void test_vector4() {
bit::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(5);
v.push_back(6);
// 正确做法：接收 erase 的返回值
auto it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) {
it = v.erase(it); // erase 返回下一个有效迭代器
} else {
++it;
}
}
// 错误做法：直接递增迭代器
// auto it = v.begin();
// while (it != v.end())
// {
// if (*it % 2 == 0)
// {
// v.erase(it);
// // erase 后 it 失效
// }
// ++it;
// // 错误：对失效迭代器递增
// }
}
不同编译器对迭代器失效的检查严格程度不同：
vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 可能引起扩容
// it 已经失效，不能再使用
vector<int> v = {1, 2, 3};
auto it = v.begin() + 2; // 指向 3
it = v.erase(it); // 删除最后一个元素
// 此时 it == v.end()，不能解引用
与 vector 类似，string 在插入、扩容操作、erase 之后，迭代器也会失效。
#pragma once
#include <iostream>
#include <cassert>
using namespace std;
namespace bit {
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(size_t n, const T& val = T()) {
reserve(n);
for (size_t i = 0; i < n; i++) {
push_back(val);
}
}
vector(int n, const T& val = T()) {
reserve(n);
for (int i = 0; i < n; i++) {
push_back(val);
}
}
// 迭代器范围构造函数
template <class InputIterator>
vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first);
++first;
}
}
// 默认构造函数
vector() = default;
// 拷贝构造函数（现代写法）
vector(const vector<T>& v) {
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
// 赋值运算符（现代写法）
vector<T>& operator=(vector<T> tmp) {
swap(tmp);
return *this;
}
// 交换两个 vector
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 clear() { _finish = _start; }
// 判断是否为空
bool empty() const { return _start == _finish; }
// 预留空间
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
if (_start) {
for (size_t i = 0; i < sz; i++) {
std::swap(tmp[i], _start[i]);
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + 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;
}
}
}
// 获取容量
size_t capacity() const { return _end_of_storage - _start; }
// 获取元素个数
size_t size() const { return _finish - _start; }
// 下标运算符
T& operator[](size_t i) {
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const {
assert(i < size());
return _start[i];
}
// 尾部添加元素
void push_back(const T& x) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
// 尾部删除元素
void pop_back() {
assert(!empty());
--_finish;
}
// 在指定位置插入元素
iterator insert(iterator pos, const T& x) {
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage) {
size_t len = pos - _start;
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;
}
// 删除指定位置元素
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
// 析构函数
~vector() {
if (_start) {
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
#include "vector.h"
#include <iostream>
using namespace std;
namespace bit {
// 打印 vector 内容
void Print(const vector<int>& v) {
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
// 测试基本操作
void test_vector1() {
cout << "测试基本操作:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v[0]++; // 修改第一个元素
Print(v);
// 范围 for 遍历
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
// 测试 insert 操作
void test_vector2() {
cout << "\n测试 insert 操作:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
Print(v);
v.insert(v.begin(), 0); // 头部插入
Print(v);
// 注意：insert 后迭代器可能失效
auto it = v.begin() + 3;
v.insert(it, 30); // 指定位置插入
Print(v);
}
// 测试 erase 操作
void test_vector3() {
cout << "\n测试 erase 操作:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
Print(v);
v.erase(v.begin()); // 删除第一个元素
Print(v);
auto it = v.begin() + 2;
v.erase(it); // 删除指定位置元素
Print(v);
}
// 测试删除特定元素（删除所有偶数）
void test_vector4() {
cout << "\n测试删除所有偶数:" << endl;
bit::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(5);
v.push_back(6);
cout << "删除前: ";
for (auto e : v) {
cout << e << " ";
}
cout << endl;
// 正确删除方法
auto it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) {
it = v.erase(it); // 接收 erase 返回值
} else {
++it;
}
}
cout << "删除后: ";
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
// 测试 resize 操作
void test_vector5() {
cout << "\n测试 resize 操作:" << endl;
bit::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(5);
v.push_back(6);
cout << "原始 vector: ";
for (auto e : v) {
cout << e << " ";
}
cout << endl;
v.resize(3); // 缩小
cout << "resize(3): ";
for (auto e : v) {
cout << e << " ";
}
cout << endl;
v.resize(20, 5); // 扩大并填充
cout << "resize(20, 5): ";
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
// 测试拷贝构造和赋值
void test_vector6() {
cout << "\n测试拷贝构造和赋值:" << endl;
bit::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
cout << "v1: ";
for (auto e : v1) {
cout << e << " ";
}
cout << endl;
// 拷贝构造
bit::vector<int> v2(v1);
cout << "v2(拷贝 v1): ";
for (auto e : v2) {
cout << e << " ";
}
cout << endl;
// 赋值操作
bit::vector<int> v3 = {10, 20, 30, 40};
v1 = v3;
cout << "v1(赋值后): ";
for (auto e : v1) {
cout << e << " ";
}
cout << endl;
// 指定大小构造
bit::vector<int> v4(10, 1);
cout << "v4(10 个 1): ";
for (auto e : v4) {
cout << e << " ";
}
cout << endl;
bit::vector<char> v5(10, 'x');
cout << "v5(10 个 x): ";
for (auto e : v5) {
cout << e << " ";
}
cout << endl;
}
// 测试 string 类型 vector
void test_vector7() {
cout << "\n测试 string 类型 vector:" << endl;
bit::vector<string> v1;
v1.push_back("111111111111111111111111");
v1.push_back("222222222222222222222222");
v1.push_back("333333333333333333333333");
v1.push_back("444444444444444444444444");
v1.push_back("555555555555555555555555");
for (auto& e : v1) {
cout << e << " ";
}
cout << endl;
}
}
int main() {
bit::test_vector1();
bit::test_vector2();
bit::test_vector3();
bit::test_vector4();
bit::test_vector5();
bit::test_vector6();
bit::test_vector7();
return 0;
}
C++ vector 基于动态数组实现，通过三个指针管理内存。核心风险是迭代器失效：insert 可能扩容使所有迭代器失效；erase 使被删位置后迭代器失效，必须通过 it=erase(it) 接收返回值。采用 2 倍扩容策略，现代写法通过 swap 实现安全拷贝。连续存储支持高效随机访问，但需警惕迭代器失效这一主要陷阱。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online