接上篇【C++篇】解密 STL 动态之魂:全面掌握 C++ vector 的高效与优雅 在现代 C++ 编程中,容器类 vector 是不可或缺的数据结构。作为一个动态数组,它提供了高效的随机访问和动态内存管理。为了加深对 vector 的理解,本文将从零开始模拟实现一个 vector,详细解析其核心机制。我们不仅会展示基础的构造、拷贝、扩展和元素插入操作,还将采用现代 C++ 的最佳实践来优化代码,尤其是在异常安全和性能上。
通过从浅入深的分步骤实现与测试,希望让读者能够全面掌握 vector 的核心逻辑与细节。本教程不仅适合初学者,也适合想深入理解 C++ STL 背后实现的开发者。
vector
,不分配任何内存。vector
。namespace W {
template<class T>
class vector {
public:
typedef T* iterator;
vector() : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr) {}
size_t size() const { return _finish - _start; }
size_t capacity() const { return _endOfStorage - _start; }
bool empty() const { return _start == _finish; }
private:
iterator _start;
iterator _finish;
iterator _endOfStorage;
};
}
void TestEmptyVector() {
W::vector<int> v;
assert(v.size() == 0); // 验证大小
assert(v.capacity() == 0); // 验证容量
assert(v.empty()); // 验证是否为空
std::cout << "TestEmptyVector passed" << std::endl;
}
TestEmptyVector passed
vector
,并使用默认值填充。namespace W {
template<class T>
class vector {
public:
typedef T* iterator;
vector(size_t n, const T& value = T()) {
_start = new T[n];
_finish = _start + n;
_endOfStorage = _finish;
for (size_t i = 0; i < n; ++i) {
_start[i] = value; // 填充默认值
}
}
size_t size() const { return _finish - _start; }
size_t capacity() const { return _endOfStorage - _start; }
bool empty() const { return _start == _finish; }
T& operator[](size_t pos) { return _start[pos]; }
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
private:
iterator _start;
iterator _finish;
iterator _endOfStorage;
};
}
void TestInitVector() {
W::vector<int> v(5, 10);
assert(v.size() == 5); // 验证大小
assert(v.capacity() == 5); // 验证容量
assert(!v.empty()); // 验证非空
for (size_t i = 0; i < 5; ++i) {
assert(v[i] == 10); // 验证默认值
}
std::cout << "TestInitVector passed" << std::endl;
}
TestInitVector passed
vector
的拷贝构造函数。vector
是否完全复制原来的内容和容量。namespace W {
template<class T>
class vector {
public:
typedef T* iterator;
vector(const vector<T>& v) {
size_t n = v.size();
_start = new T[n];
_finish = _start + n;
_endOfStorage = _finish;
for (size_t i = 0; i < n; ++i) {
_start[i] = v._start[i]; // 复制数据
}
}
size_t size() const { return _finish - _start; }
size_t capacity() const { return _endOfStorage - _start; }
bool empty() const { return _start == _finish; }
T& operator[](size_t pos) { return _start[pos]; }
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
private:
iterator _start;
iterator _finish;
iterator _endOfStorage;
};
}
void TestCopyVector() {
W::vector<int> v1(5, 10);
W::vector<int> v2(v1);
assert(v2.size() == 5); // 验证大小
assert(v2.capacity() == 5); // 验证容量
for (size_t i = 0; i < 5; ++i) {
assert(v2[i] == 10); // 验证数据拷贝
}
std::cout << "TestCopyVector passed" << std::endl;
}
TestCopyVector passed
vector
赋值后,是否正确拷贝了内容和容量。namespace W {
template<class T>
class vector {
public:
typedef T* iterator;
vector<T>& operator=(const vector<T>& v) {
if (this != &v) {
delete[] _start; // 释放旧的空间
size_t n = v.size();
_start = new T[n];
_finish = _start + n;
_endOfStorage = _finish;
for (size_t i = 0; i < n; ++i) {
_start[i] = v._start[i]; // 复制数据
}
}
return *this;
}
size_t size() const { return _finish - _start; }
size_t capacity() const { return _endOfStorage - _start; }
bool empty() const { return _start == _finish; }
T& operator[](size_t pos) { return _start[pos]; }
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
private:
iterator _start;
iterator _finish;
iterator _endOfStorage;
};
}
void TestAssignVector() {
W::vector<int> v1(5, 10);
W::vector<int> v2 = v1; // 赋值操作
assert(v2.size() == 5); // 验证大小
assert(v2.capacity() == 5); // 验证容量
for (size_t i = 0; i < 5; ++i) {
assert(v2[i] == 10); // 验证数据拷贝
}
std::cout << "TestAssignVector passed" << std::endl;
}
TestAssignVector passed
reserve
函数:动态扩容reserve
函数,测试在容量不足时是否能正确扩展。namespace W {
template<class T>
class vector {
public:
void reserve(size_t n) {
if (n > capacity()) {
size_t oldSize = size();
T* tmp = new T[n];
for (size_t i = 0; i < oldSize; ++i) {
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + oldSize;
_endOfStorage = _start + n;
}
}
};
}
void TestReserveVector() {
W::vector<int> v(5, 10);
v.reserve(10); // 预留容量
assert(v.capacity() == 10); // 验证容量扩展
for (size_t i = 0; i < 5; ++i) {
assert(v[i] == 10); // 验证数据保持不变
}
std::cout << "TestReserveVector passed" << std::endl;
}
TestReserveVector passed
resize
函数:改变大小resize
函数,测试增加或减少vector
大小。namespace W {
template<class T>
class vector {
public:
void resize(size_t n, const T& value = T()) {
if (n < size()) {
_finish = _start + n; // 缩小大小
} else {
reserve(n);
for (iterator it = _finish; it != _start + n; ++it)
{
*it = value; // 填充新值
}
_finish = _start + n;
}
}
};
}
void TestResizeVector() {
W::vector<int> v(5, 10);
v.resize(8, 20); // 扩展大小并填充新值
assert(v.size() == 8); // 验证扩展后大小
for (size_t i = 0; i < 5; ++i) {
assert(v[i] == 10); // 验证原值不变
}
for (size_t i = 5; i < 8; ++i) {
assert(v[i] == 20); // 验证新值
}
std::cout << "TestResizeVector passed" << std::endl;
}
TestResizeVector passed
push_back
函数:向vector
末尾插入元素push_back
是vector
中最常用的操作之一。需要确保: _finish
指针,指向新的末尾。namespace W {
template<class T>
class vector {
public:
void push_back(const T& x) {
// 如果空间不足,扩展容量为当前容量的两倍
if (_finish == _endOfStorage) {
size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
reserve(newCapacity);
}
// 在末尾插入新元素
*_finish = x;
++_finish;
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestPushBackVector() {
W::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
assert(v.size() == 3); // 验证插入后的大小
assert(v.capacity() >= 3); // 验证容量是否自动扩展
assert(v[0] == 1 && v[1] == 2 && v[2] == 3); // 验证插入的元素是否正确
std::cout << "TestPushBackVector passed" << std::endl;
}
TestPushBackVector passed
pop_back
函数:删除末尾元素pop_back
用于删除vector
中的最后一个元素。需要确保: _finish
指针。_finish
指针向前移动一位,即删除最后一个元素。namespace W {
template<class T>
class vector {
public:
void pop_back() {
assert(_finish != _start); // 确保vector非空
--_finish; // 逻辑删除最后一个元素
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestPopBackVector() {
W::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.pop_back();
assert(v.size() == 2); // 验证删除后的大小
assert(v[0] == 1 && v[1] == 2); // 验证剩余元素是否正确
std::cout << "TestPopBackVector passed" << std::endl;
}
TestPopBackVector passed
insert
函数:在指定位置插入元素insert
用于在vector
的任意位置插入元素。需要确保: _finish
指针。namespace W {
template<class T>
class vector {
public:
T* insert(T* pos, const T& value) {
assert(pos >= _start && pos <= _finish); // 确保pos是有效指针
// 检查空间是否足够
if (_finish == _endOfStorage) {
size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
size_t offset = pos - _start; // 记录插入位置
reserve(newCapacity); // 扩容
pos = _start + offset; // 更新插入位置
}
// 将插入位置之后的元素整体向后移动
for (T* it = _finish; it > pos; --it) {
*it = *(it - 1);
}
// 插入新元素
*pos = value;
++_finish;
return pos;
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestInsertVector() {
W::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.insert(v.begin() + 2, 3); // 在第2个位置插入3
assert(v.size() == 4); // 验证插入后的大小
assert(v[0] == 1 && v[1] == 2 && v[2] == 3 && v[3] == 4); // 验证插入的元素是否正确
std::cout << "TestInsertVector passed" << std::endl;
}
TestInsertVector passed
erase
函数:删除指定位置的元素erase
用于删除vector
中的某个位置的元素。需要确保: _finish
指针。erase
位置之后的元素向前移动一位。_finish
指针。namespace W {
template<class T>
class vector {
public:
T* erase(T* pos) {
assert(pos >= _start && pos < _finish); // 确保pos是有效指针
// 将pos之后的元素向前移动
for (T* it = pos; it < _finish - 1; ++it) {
*it = *(it + 1);
}
--_finish; // 更新_finish指针
return pos;
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestEraseVector() {
W::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.erase(v.begin() + 2); // 删除第2个元素
assert(v.size() == 3); // 验证删除后的大小
assert(v[0] == 1 && v[1] == 2 && v[2] == 4); // 验证删除后的元素顺序
std::cout << "TestEraseVector passed" << std::endl;
}
TestEraseVector passed
front
和back
函数front
函数:获取第一个元素front
函数返回vector
的第一个元素。需要确保: vector
非空时,返回正确的第一个元素。namespace W {
template<class T>
class vector {
public:
T& front() {
assert(!empty()); // 确保vector非空
return *_start; // 返回第一个元素
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestFrontVector() {
W::vector<int> v;
v.push_back(10);
assert(v.front() == 10); // 验证front
v.push_back(20);
assert(v.front() == 10); // 验证front不变
std::cout << "TestFrontVector passed" << std::endl;
}
TestFrontVector passed
back
函数:获取最后一个元素back
函数返回vector
的最后一个元素。需要确保: vector
非空时,返回正确的最后一个元素。namespace W {
template<class T>
class vector {
public:
T& back() {
assert(!empty()); // 确保vector非空
return *(_finish - 1); // 返回最后一个元素
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestBackVector() {
W::vector<int> v;
v.push_back(10);
assert(v.back() == 10); // 验证back
v.push_back(20);
assert(v.back() == 20); // 验证back变化
std::cout << "TestBackVector passed" << std::endl;
}
TestBackVector passed
begin
与 end
函数:迭代器的基本操作begin
函数返回指向 vector
起始位置的迭代器(即指向第一个元素)。end
函数返回指向 vector
末尾的迭代器(即指向最后一个元素的下一个位置)。vector
中的元素。namespace W {
template<class T>
class vector {
public:
typedef T* iterator; // 使用原生指针作为迭代器
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestIteratorVector() {
W::vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
// 使用迭代器遍历 vector
for (W::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
std::cout << "TestIteratorVector passed" << std::endl;
}
10 20 30
TestIteratorVector passed
swap
函数:交换两个 vector
swap
函数用于交换两个 vector
的内容,包括它们的起始指针、结束指针和容量指针。swap
函数是常用的优化操作,特别是在实现移动语义时能大大提高效率。namespace W {
template<class T>
class vector {
public:
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
void TestSwapVector() {
W::vector<int> v1;
W::vector<int> v2;
v1.push_back(1);
v1.push_back(2);
v2.push_back(3);
v2.push_back(4);
v1.swap(v2);
// 验证 v1 和 v2 交换后内容是否正确
for (auto e : v1) {
std::cout << e << " ";
}
std::cout << std::endl;
for (auto e : v2) {
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << "TestSwapVector passed" << std::endl;
}
3 4
1 2
TestSwapVector passed
vector
(现代写法)vector
,并确保与原 vector
独立,使用深拷贝拷贝元素。赋值运算符重载代码大致也是相同的,那有没有办法简化呢?swap
函数,使代码简洁高效,且异常安全。namespace W {
template<class T>
class vector {
public:
//这里可以服用reserve和push_back函数了
vector(const vector<T>& v)
: _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
{
reserve(v.size()); // 分配所需空间
for (const T& elem : v) {
push_back(elem); // 拷贝每个元素
}
}
// 赋值操作符,使用拷贝并交换技术
vector<T>& operator=(vector<T> v) {
swap(v); // 调用 swap 函数交换内容
return *this;
}
// swap 函数
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
// 其他成员函数同之前实现...
private:
T* _start;
T* _finish;
T* _endOfStorage;
};
}
vector<T>
的值作为参数,创建一个临时对象 v
。调用拷贝构造函数时自动执行拷贝,然后在赋值操作中与现有对象交换内容。传值是安全的,避免了手动内存管理问题。_start
、_finish
和 _endOfStorage
,避免手动内存释放,简化代码逻辑。交换后的临时对象 v
离开作用域时自动销毁,保证资源释放。void TestCopyAndAssignVector() {
// 测试拷贝构造函数
W::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
W::vector<int> v2(v1); // 使用拷贝构造函数
for (size_t i = 0; i < v2.size(); ++i) {
assert(v2[i] == v1[i]); // 验证每个元素是否相同
}
// 测试赋值操作符
W::vector<int> v3;
v3 = v1; // 使用赋值操作符
for (size_t i = 0; i < v3.size(); ++i) {
assert(v3[i] == v1[i]); // 验证每个元素是否相同
}
std::cout << "TestCopyAndAssignVector passed" << std::endl;
}
TestCopyAndAssignVector passed
swap
,避免了重复的深拷贝代码。