C++实现vector
1. 迭代器与内存布局
Vector通过原生指针实现迭代器，三个核心指针构成内存布局：
typedef T* iterator;
typedef const T* const_iterator;
iterator _start = nullptr; // 数据块起始位置
iterator _finish = nullptr; // 有效数据末尾的下一位
iterator _end_of_storage = nullptr; // 内存块末尾的下一位
1.1 迭代器实现
//指向第一个元素
iterator begin()
{
return _start;
}
//指向最后一个元素的下一个元素
iterator end()
{
return _finish;
}
const_iterator cbegin()
{
return _start;
}
const_iterator cend() const
{
return _finish;
}
2. 关键构造与析构
2.1 构造函数
// 默认构造
vector() = default;
// 填充构造：n个value
vector(int n, const T & value = T()) {
reserve(n);
for (size_t i = 0; i < n; i++) {
push_back(value);
}
}
// 使用任意容器类型的的迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first); // 自动扩容
first++;
}
}
2.2 析构函数
~vector() {
if(_start) {
delete[] _start; // 释放连续内存
_start = _finish = _end_of_storage = nullptr;
}
}
3. 拷贝、赋值与交换
3.1 拷贝构造
通过遍历实现深拷贝：
vector(const vector<T>& v) {
for (size_t i = 0; i < v.size(); i++) {
push_back(v[i]); // 元素逐个复制
}
}
3.2 赋值运算符
易错：
vector<T>& operator=(vector<T> v) {
swap(v);
// 缺少return语句！
}
问题分析：
- 未返回
*this，导致链式赋值失败（如a=b=c） - 未处理自赋值（虽因copy-swap避免，但效率低）
解决方案：
vector<T>& operator=(const vector<T>& v) {
if(this != &v) { // 自赋值检查
// 深拷贝实现
}
return *this;
}
最终代码：
vector<T>& operator= (vector<T> v) {
if(this!= v)
{
swap(v); // 交换临时副本与当前对象
return *this;
}
return *this
}
//交换元素
void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
4. 动态扩容机制
reserve() 是扩容核心，需处理内存拷贝。
4.1 reserve浅拷贝问题
void reserve(size_t n) {
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * oldsize); // 危险！
}
问题分析：
memcpy执行位拷贝，若T是含资源的对象（如string/vector），会导致：
- 原对象资源泄漏（未调用析构函数）
- 新对象双重释放（拷贝的指针指向同一内存）
解决方案：
// 手动拷贝构造每个元素
for(size_t i = 0; i < oldsize; ++i) {
tmp[i] = _start[i]; // 调用T::operator=
}
最终代码：
void reserve(size_t n) {
size_t oldsize = size();
if (n > capacity()) {
T* tmp = new T[n]; // 申请新内存
if(_start) {
memcpy(tmp, _start, sizeof(T) * oldsize); // 数据拷贝
delete[] _start; // 释放旧内存
}
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
4.2 resize() 调整元素数量
void resize(size_t n, const T& value = T()) {
if (n < size()) {
_finish = _start + n; // 缩减元素
} else {
reserve(n);
while (_finish != _start + n) {//如果使用end != _end_of_storage，本意是想追加到第n个位置即到_start+n位置,该位置<=_end_of_storage,否则就是全部填充value
*_finish = value; // 填充默认值
++_finish;
}
}
}
5. 元素访问与修改
5.1 随机访问
通过运算符重载实现：
T& operator[](size_t pos) {
assert(pos < size()); // 边界检查
return _start[pos];
}
5.2 尾删尾插
void push_back(const T& x) {
if (_finish == _end_of_storage) {
size_t newcapacity = capacity() ? 2 * capacity() : 4;
reserve(newcapacity); // 2倍扩容策略
}
*_finish++ = x; // 尾部插入
}
void pop_back() {
assert(_finish > _start);
--_finish; // 仅移动指针
}
6. 任意位置插入删除
6.1 insert()
需处理迭代器失效
问题：
void insert(iterator pos, const T& x) {
reserve(newcapacity); // 扩容后
// 原pos指针失效！
}
问题分析：
- 扩容重新分配内存后，原有迭代器/引用全部失效
- 未更新
pos导致后续操作访问已释放内存
解决方案：
size_t offset = pos - _start; // 保存偏移量
reserve(newcapacity);
pos = _start + offset; // 重定位
最终代码：
iterator insert(iterator pos, const T& x) {
assert(pos >= begin() && pos <= end());
if (size() == capacity()) {
size_t offset = pos - _start; // 保存相对位置
reserve(capacity() ? 2 * capacity() : 4);
pos = _start + offset; // 重置失效迭代器
}
iterator end = _finish;
while (end > pos) {
*end = *(end - 1); // 元素后移
--end;
}
*pos = x;
++_finish;
return pos;
}
6.2 erase()
前移覆盖元素：
iterator erase(iterator pos) {
assert(pos >= begin() && pos < end());
iterator it = pos;
while (it < _finish - 1) {//it==_finish-2时，已经将_finish - 1即最后一个元素前移
*it = *(it + 1); // 元素前移
++it;
}
--_finish;
return pos;
}
7 易错点
| 易错点 | 问题描述 | 错误代码示例 | 正确解决方案 |
|---|---|---|---|
| 浅拷贝问题 | 使用memcpy拷贝含资源的对象导致资源泄漏/双重释放 | memcpy(tmp, _start, sizeof(T)*oldsize); | 改用元素级拷贝：for(i=0;i<oldsize;++i) tmp[i]=_start[i]; |
| 迭代器失效 | 扩容后未更新已保存的迭代器位置 | reserve(newcap);后直接使用原pos | 保存偏移量：size_t offset=pos-_start;reserve后pos=_start+offset; |
| 赋值运算符错误 | 缺少返回值或未处理自赋值 | vector<T>& operator=(vector<T> v){swap(v);}(缺少 return *this;) | 添加返回值并检查自赋值：if(this!=&v){...} return *this; |
| resize低效 | 多次调用push_back导致重复扩容 | resize(n){... while(...) push_back(value);} | 直接批量初始化：reserve(n);while(_finish!=_start+n) *_finish++=value; |
| 自赋值问题 | 未处理v=v导致不必要的拷贝 | 赋值运算符未检查自赋值 | 添加自赋值检查：if(this==&v) return *this; |
原文地址：https://blog.csdn.net/weixin_47208237/article/details/149122665
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！