本文详细介绍了C++标准模板库(STL)中的vector容器。作为最常用的序列容器之一，vector提供了类似动态数组的功能，支持高效的元素访问与动态扩容。我们将系统学习其常用接口、核心特性，并深入探讨迭代器失效问题，最后通过一个完整的模拟实现来剖析其底层原理。
一、标准库中的vector类模板
vector是一个表示可变大小数组的序列容器。它像string一样，底层通过动态开辟的数组实现。
核心特点：
- 高效访问：可以使用下标（
operator[]）随机访问元素，效率与数组相当。
- 动态扩容：其大小可以动态变化。当插入新元素导致空间不足时，容器会自动分配更大的内存空间，并将原有元素“迁移”过去。为了平衡性能，扩容通常按指数级进行，使得在尾部插入元素的均摊时间复杂度为O(1)。
- 尾部操作高效：在末尾进行插入(
push_back)和删除(pop_back)操作效率很高。在中间或头部进行插入删除则效率较低。
- 连续存储：元素在内存中是连续存储的，这带来了良好的缓存局部性，也是其高效访问的根源。
注：使用vector类必须包含头文件#include <vector>，并使用std命名空间。你可以将 string 类近似理解为 vector<char> 的一个特化版本，两者在接口设计和使用上有很多相似之处，这对于理解算法与数据结构中的容器概念很有帮助。
二、vector类的常用接口
构造函数
vector提供了多种构造函数来满足不同初始化需求。
int main()
{
vector<int> v; // (1) 默认无参构造
vector<int> v1(4); // (2) 创建4个元素，默认值为0
// vector<int> v2 = 4; // 错误！explicit构造函数禁止隐式转换
vector<int> v3(4, 10); // (2) 创建4个元素，每个值指定为10
vector<int> v4(v1); // (4) 拷贝构造
vector<int> v5(v1.begin(), v1.end()); // (3) 使用迭代器范围初始化
// (5) C++11支持的列表初始化
vector<int> v6{ 1,2,3,4 };
vector<int> v7 = { 1,2,3,4 }; // 与v6等价
}
容量操作函数
容量相关函数用于管理vector的内存和大小。
| 函数名 |
功能说明 |
| size |
获取容器中当前元素的个数。 |
| capacity |
获取容器的当前容量（总共能容纳多少元素而不扩容）。 |
| resize |
调整容器中元素的数量(size)。 |
| reserve |
调整容器的容量(capacity)，预留空间。 |
| empty |
判断容器是否为空。 |
| clear |
清空所有元素（size变为0，capacity通常不变）。 |
int main()
{
vector<int> v(4, 10);
cout << v.size() << " " << v.capacity() << endl; // 输出：4 4
v.reserve(10); // 预留容量为10
cout << v.size() << " " << v.capacity() << endl; // 输出：4 10
v.resize(20); // 将大小调整为20，新增元素默认初始化为0
cout << v.size() << " " << v.capacity() << endl; // 输出：20 20
cout << v.empty() << endl; // 输出：0 (false)
return 0;
}
访问及遍历操作函数
vector提供了多种灵活的方式来访问和遍历元素。
| 函数名 |
功能说明 |
| operator[] |
像数组一样通过下标访问，不进行边界检查。 |
| at |
访问指定位置元素，会进行边界检查，越界则抛出out_of_range异常。 |
| front |
访问第一个元素。 |
| back |
访问最后一个元素。 |
| begin / end |
获取指向第一个元素的迭代器和末尾元素之后位置的迭代器。 |
| rbegin / rend |
获取反向迭代器。 |
int main()
{
vector<int> v{1,2,3,4}; // 列表初始化
// 1. 下标遍历
for (size_t i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
// 2. 正向迭代器遍历
vector<int>::iterator it = v.begin(); // 也可使用 auto it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
// 3. 反向迭代器遍历
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
cout << *rit << " ";
}
cout << endl;
// 4. 范围for循环 (C++11)
for (auto e : v) {
cout << e << " ";
}
return 0;
}
增删查改
这些是vector最核心的修改操作。
| 函数名 |
功能说明 |
| push_back |
在容器尾部插入一个元素。 |
| pop_back |
删除容器尾部的一个元素。 |
| insert |
在指定迭代器位置之前插入一个或多个元素。 |
| erase |
删除指定迭代器位置的一个元素，或一个迭代器区间的元素。 |
| swap |
交换两个vector容器的内容。 |
| find |
注意：这是<algorithm>中的通用算法，不是vector的成员函数。 |
#include <algorithm> // 使用std::find, std::sort
int main()
{
vector<int> v(4, 10);
vector<int> v2(2, 3);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.pop_back(); // 删除末尾的3
v.insert(v.begin(), 1); // 在开头插入1
v.insert(v.begin(), 5, 2); // 在开头插入5个2
v.erase(v.begin()); // 删除第一个元素
v.erase(v.begin(), v.begin() + 5); // 删除区间[first, last)的元素
v.swap(v2); // 成员函数swap
swap(v, v2); // 非成员函数swap，效果相同
auto it = find(v.begin(), v.end(), 2); // 查找值为2的元素，返回迭代器
sort(v.begin(), v.end()); // 对vector进行排序
return 0;
}
迭代器失效问题
迭代器本质上是一个指针或对指针的封装，它指向容器中的某个元素。迭代器失效意味着迭代器所指向的内存空间变得无效（例如被释放），继续使用它将导致未定义行为（通常是程序崩溃）。
导致失效的常见操作：
- 引起底层空间重新分配的操作：如
reserve、resize、push_back（当容量不足时）、insert（当容量不足时）等。这些操作可能导致内存地址改变，使所有迭代器、指针、引用失效。
- 指定位置的删除操作：
erase操作会删除元素，使得被删除元素及其之后位置的迭代器失效。
关键点：解决迭代器失效的方法是，在执行可能引起失效的操作后，对迭代器进行重新赋值（例如重新调用begin()、find()等获取新的迭代器）。
int main()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);
if (pos != v.end()) {
// v.insert(pos, 20); // 插入操作可能导致扩容，使pos失效
v.erase(pos); // 删除操作使pos及其后迭代器失效
}
// 失效后，下面的访问是危险的！
// cout << *pos << endl; // 未定义行为
// *pos = 10; // 未定义行为
// 正确做法：在insert/erase后，如果需要继续使用，应更新pos
// pos = v.insert(pos, 20); // insert会返回指向新插入元素的迭代器
// pos = v.erase(pos); // erase会返回指向被删除元素下一个位置的迭代器
return 0;
}
三、vector深度剖析及模拟实现
理解vector的底层实现是掌握其特性和规避陷阱的关键。下面我们实现一个简化版的vector类模板。
核心框架与迭代器
namespace myvector
{
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; }
private:
iterator _start = nullptr; // 指向数组首元素
iterator _finish = nullptr; // 指向最后一个有效元素的下一个位置 (size)
iterator _endofstorage = nullptr; // 指向存储空间尾部的下一个位置 (capacity)
};
}
构造函数与析构函数
public:
// 默认构造
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
// 迭代器范围构造
template <class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last) {
push_back(*first);
++first;
}
}
// 拷贝构造（现代写法）
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end()); // 用v的数据构造tmp
swap(tmp); // 交换*this和tmp的资源
}
// 赋值运算符重载（现代写法）
vector<T>& operator=(vector<T> v) { // 传参时调用拷贝构造
swap(v); // 交换*this和副本v的资源
return *this; // 出作用域后v（原*this资源）被析构
}
// 析构函数
~vector() {
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
容量与大小操作
public:
size_t size() const {
return _finish - _start;
}
size_t capacity() const {
return _endofstorage - _start;
}
void reserve(size_t n) {
if (n > capacity()) {
size_t old_sz = size();
T* tmp = new T[n]; // 开辟新空间
// 拷贝数据（注意：如果T是自定义类型且深拷贝，memcpy可能有问题）
// 这里使用循环构造更安全
for(size_t i = 0; i < old_sz; ++i) {
tmp[i] = _start[i];
}
delete[] _start; // 释放旧空间
_start = tmp;
_finish = _start + old_sz;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& val = T()) {
if (n <= size()) {
_finish = _start + n; // 缩小
} else {
if (n > capacity()) {
reserve(n);
}
iterator it = _finish;
_finish = _start + n;
while (it < _finish) {
*it = val;
++it;
}
}
}
元素访问与修改
public:
T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const {
assert(pos < size());
return _start[pos];
}
void push_back(const T& x) {
// 常规写法：
// if (_finish == _endofstorage) {
// size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(new_capacity);
// }
// *_finish = x;
// ++_finish;
// 复用insert
insert(end(), x);
}
void pop_back() {
// 常规写法：
// assert(_finish > _start);
// --_finish;
// 复用erase
erase(end() - 1);
}
插入与删除（核心与失效处理）
public:
iterator insert(iterator pos, const T& val) {
assert(pos >= _start && pos <= _finish); // 可以等于_finish（即尾插）
// 检查扩容
if (_finish == _endofstorage) {
size_t len = pos - _start; // 记录pos的相对位置！！！
size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(new_capacity);
pos = _start + len; // 关键！扩容后更新pos，防止迭代器失效
}
// 从后向前移动元素
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos; // 返回指向新插入元素的迭代器
}
iterator erase(iterator pos) {
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos; // 返回指向被删除元素下一个位置的迭代器
}
工具函数
public:
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
bool empty() const {
return _start == _finish;
}
模拟实现总结：
这个简化实现涵盖了vector最核心的机制：动态数组管理、迭代器、容量增长、以及在insert/erase中处理迭代器失效。理解这些底层细节不仅能帮你更好地使用STL容器，也是提升系统编程中内存管理能力的重要一步。注意，生产级别的实现会更加复杂，需处理异常安全、优化拷贝、支持分配器等。
发表于 2025-12-26 10:08:37
|
查看: 33|
回复: 0
