1. 深入解析C++ vector类的模拟实现（下）
在上一篇文章中，我们已经完成了vector类的基础骨架搭建，包括类模板设计、三个核心指针的作用以及基础接口的实现。今天我们将继续深入探讨vector类的构造函数、拷贝控制、元素插入和删除等更复杂的操作。
1.1 构造函数实现详解
1.1.1 普通构造函数的实现
vector的普通构造函数需要处理两个关键参数：元素个数n和初始值val。其核心设计思路如下：
cpp复制vector(size_t n = 1, const type1& val = type1())
{
reserve(n);
for(size_t i = 0; i < n; ++i) {
push_back(val);
}
}
这个实现有几个关键点需要注意：
-
默认参数设计：val使用
const type1&类型，避免不必要的拷贝开销，同时默认值为type1()，可以适配所有类型的初始化需求。 -
内存预分配：先调用
reserve(n)确保有足够空间，避免后续插入时的频繁扩容。 -
元素初始化：通过循环调用
push_back来初始化元素，确保每个元素都经过正确的构造过程。
为什么不用new直接分配空间？
与string不同，vector需要处理任意类型的数据。直接使用
new type1[n]会带来两个问题：
- 对于没有默认构造函数的类型会编译失败
- 无法保证元素的正确初始化（特别是对于需要深拷贝的自定义类型）
1.1.2 迭代器范围构造函数
为了实现更灵活的初始化方式，我们还需要实现一个接受迭代器范围的构造函数：
cpp复制template <typename InputIterator>
vector(InputIterator begin, InputIterator end)
{
ptrdiff_t count = std::distance(begin, end);
reserve(count);
while(begin != end) {
push_back(*begin);
++begin;
}
}
这个构造函数的亮点在于：
- 模板参数：可以接受任何类型的迭代器（vector、list、deque等）
- 通用性：通过
std::distance计算元素数量，适配不同迭代器类型 - 效率：预先分配足够空间，避免插入时的多次扩容
1.2 拷贝控制实现
1.2.1 现代写法的拷贝构造函数
现代C++推荐使用"拷贝-交换"惯用法来实现拷贝构造函数：
cpp复制vector(const vector<type1>& v)
{
vector<type1> temp(v.begin(), v.end());
swap(temp);
}
void swap(vector<type1>& other)
{
std::swap(mstart, other.mstart);
std::swap(mfinish, other.mfinish);
std::swap(mend_of_storage, other.mend_of_storage);
}
这种实现方式的优势在于：
- 异常安全：所有可能抛出异常的操作都在temp对象中完成
- 代码复用：复用迭代器范围构造函数
- 自动资源管理：temp对象在函数结束时自动释放原资源
1.2.2 赋值运算符重载
赋值运算符可以复用拷贝构造函数的实现：
cpp复制vector<type1>& operator=(const vector<type1>& v)
{
vector<type1> temp(v);
swap(temp);
return *this;
}
这种实现自动处理了自赋值情况，并且提供了强异常安全保证。
1.3 元素操作实现
1.3.1 insert函数实现
insert函数是vector中最复杂的操作之一，主要难点在于处理迭代器失效问题：
cpp复制iterator insert(iterator pos, const type1& val = type1())
{
assert(pos <= mfinish);
assert(pos >= mstart);
if(mfinish == mend_of_storage) {
size_t offset = pos - mstart;
size_t new_capacity = capacity() ? 2 * capacity() : 2;
reserve(new_capacity);
pos = mstart + offset;
}
iterator it = mfinish - 1;
while(it != pos) {
*(it + 1) = *it;
--it;
}
*pos = val;
++mfinish;
return pos;
}
关键点解析：
- 迭代器失效处理：在扩容前记录pos的偏移量，扩容后重新计算pos位置
- 元素移动：从后向前移动元素，避免覆盖问题
- 返回值：返回指向新插入元素的迭代器，符合STL标准
1.3.2 erase函数实现
erase函数相对简单，但需要注意迭代器失效问题：
cpp复制void erase(iterator pos)
{
assert(!empty());
assert(pos < mfinish);
assert(pos >= mstart);
size_t index = pos - mstart;
for(size_t i = index; i < size() - 1; ++i) {
mstart[i] = mstart[i + 1];
}
--mfinish;
}
注意事项：
- 边界检查：确保容器不为空且pos在有效范围内
- 元素移动：从前向后移动元素，覆盖要删除的元素
- 迭代器失效：删除后原pos迭代器失效，不应再使用
1.4 实现细节与优化技巧
1.4.1 内存管理优化
在实际工程中，vector的内存管理可以进一步优化：
- 小对象优化：对于小型vector，可以使用栈空间避免堆分配
- 内存池：对于频繁分配释放的场景，可以使用内存池提高性能
- 移动语义：C++11后应实现移动构造函数和移动赋值运算符
1.4.2 异常安全保证
不同操作应提供不同级别的异常安全保证：
- 基本保证：操作失败后容器仍处于有效状态
- 强保证：操作要么完全成功，要么不影响容器状态
- 不抛保证：操作保证不会抛出异常
1.5 常见问题与解决方案
1.5.1 迭代器失效场景
vector操作中会导致迭代器失效的情况包括：
- 插入操作：可能导致所有迭代器失效（扩容时）
- 删除操作：被删除元素之后的迭代器失效
- 扩容操作：所有迭代器失效
解决方案：
- 操作后重新获取迭代器
- 使用索引代替迭代器
- 预留足够空间避免扩容
1.5.2 性能优化建议
- 预分配空间：提前调用reserve减少扩容次数
- 批量操作：优先使用范围插入而非单个插入
- 移动语义：对于临时对象使用std::move减少拷贝
1.6 完整代码实现
以下是vector类的完整实现代码：
cpp复制template <typename T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
// 构造函数
vector(size_t n = 1, const T& val = T()) {
reserve(n);
for(size_t i = 0; i < n; ++i) {
push_back(val);
}
}
template <typename InputIterator>
vector(InputIterator begin, InputIterator end) {
ptrdiff_t count = std::distance(begin, end);
reserve(count);
while(begin != end) {
push_back(*begin);
++begin;
}
}
// 拷贝控制
vector(const vector<T>& v) {
vector<T> temp(v.begin(), v.end());
swap(temp);
}
vector<T>& operator=(const vector<T>& v) {
vector<T> temp(v);
swap(temp);
return *this;
}
~vector() {
if(mstart) {
delete[] mstart;
mstart = mfinish = mend_of_storage = nullptr;
}
}
// 容量操作
size_t size() const { return mfinish - mstart; }
size_t capacity() const { return mend_of_storage - mstart; }
bool empty() const { return mstart == mfinish; }
void reserve(size_t n) {
if(n > capacity()) {
size_t old_size = size();
iterator temp = new T[n];
std::copy(begin(), end(), temp);
delete[] mstart;
mstart = temp;
mfinish = mstart + old_size;
mend_of_storage = mstart + n;
}
}
// 元素访问
T& operator[](size_t pos) { return mstart[pos]; }
const T& operator[](size_t pos) const { return mstart[pos]; }
// 迭代器
iterator begin() { return mstart; }
iterator end() { return mfinish; }
const_iterator begin() const { return mstart; }
const_iterator end() const { return mfinish; }
// 修改操作
void push_back(const T& val) {
if(mfinish == mend_of_storage) {
reserve(capacity() ? 2 * capacity() : 2);
}
*mfinish = val;
++mfinish;
}
iterator insert(iterator pos, const T& val = T()) {
assert(pos <= mfinish);
assert(pos >= mstart);
if(mfinish == mend_of_storage) {
size_t offset = pos - mstart;
size_t new_capacity = capacity() ? 2 * capacity() : 2;
reserve(new_capacity);
pos = mstart + offset;
}
iterator it = mfinish - 1;
while(it != pos) {
*(it + 1) = *it;
--it;
}
*pos = val;
++mfinish;
return pos;
}
void erase(iterator pos) {
assert(!empty());
assert(pos < mfinish);
assert(pos >= mstart);
size_t index = pos - mstart;
for(size_t i = index; i < size() - 1; ++i) {
mstart[i] = mstart[i + 1];
}
--mfinish;
}
void swap(vector<T>& other) {
std::swap(mstart, other.mstart);
std::swap(mfinish, other.mfinish);
std::swap(mend_of_storage, other.mend_of_storage);
}
private:
iterator mstart = nullptr;
iterator mfinish = nullptr;
iterator mend_of_storage = nullptr;
};
1.7 实际应用中的注意事项
在实际项目中使用自定义vector时，需要注意以下几点：
- 异常安全：确保在异常发生时资源能被正确释放
- 类型要求：模板类型T必须满足可拷贝构造和可赋值
- 性能考量：频繁插入删除时考虑使用list或deque
- 内存管理：大型vector要注意内存碎片问题
通过本文的详细解析，相信大家对C++ vector的内部实现有了更深入的理解。掌握这些底层知识不仅能帮助我们在面试中脱颖而出，更能提升我们日常开发中对STL容器的使用水平。