当前位置：首页 > news >正文

vector模拟实现

news 2026/4/20 2:57:44

迭代器失效

我们先实现一个简单的vector逻辑

#pragma once #include<assert.h> #include<iostream>  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() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { }  ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } }    void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n;  } }  size_t capacity() const { return _endofstorage - _start; }  size_t size() const { return _finish - _start; }  T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; }  const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } private: iterator _start; iterator _finish; iterator _endofstorage; }; }

迭代器失效1-扩容

在此基础上增加push_back和insert

 void push_back(const T& x) { //if (_finish == _endofstorage) //{ // size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; // reserve(newcapacity); //} //*_finish = x; //++_finish;  insert(end(), x); }  void insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish);  if (_finish == _endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); }  iterator end = _finish - 1;  while (end >= pos) { *(end + 1) = *end; end--; }  *pos = x; ++_finish; }

这里push_back在调用insert时，就会出现一个典型问题：迭代器失效

当push_back 调用insert时，若需要扩容，则会进入reserve()；

reserve()内部delete[]释放旧数组内存，_start指向新地址；

返回insert后，原来的pos位置（即旧finish的地址）已经指向被释放的内存，成为野指针，后续再对pos访问会导致未定义行为

解决方案：在可能引起扩容的操作之前，记录迭代器的相对位置（偏移量），扩容后重新计算新的迭代器。

void insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish);  if (_finish == _endofstorage) { size_t offset = pos - _start;//记录pos相对位置 size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity);  pos = _start + offset;//更新pos }  iterator end = _finish - 1;  while (end >= pos) { *(end + 1) = *end; end--; }  *pos = x; ++_finish; }

此时解决了vector内部的迭代器失效问题，但是外部调用时，使用insert后迭代器仍可能失效（扩容）。

insert后不要再次使用形参迭代器。

C++标准库采用了iterator返回值方式来解决

iterator insert(iterator pos, const T& x) {  ... return pos; }

迭代器失效2-删除

接下来看一个删除的场景

void erase(iterator pos) { assert(pos >= _start && pos < _finish);  iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; it++; } --_finish; }

对erase进行调用

void test_2() { bit::vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); for (auto e : v1) { cout << e << " "; } cout << endl;  v1.erase(v1.begin() + 4); //erase后，迭代器失效，vs强制检查访问 auto it = v1.begin() + 4; v1.erase(it); cout << *it << endl;//未定义操作 it--;//未定义操作 cout << *it << endl;//未定义操作   }

erase后，it仍保留原来的内存地址，但这个地址已经不在容器有效范围内，it变成悬空迭代器；尽管--it后，仍能访问容器中的元素，但是在标准语义中，此时的it已经是失效迭代器，对it的任何操作都是未定义行为，尽管it可能和容器物理上紧邻。

vs中会强制检查erase后的迭代器，不允许对其再次访问

正确写法是返回迭代器

iterator erase(iterator pos) { assert(pos >= _start && pos < _finish);  iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; it++; } --_finish; return pos; }

深浅拷贝

拷贝构造与复制拷贝

//vector(const vector<T>& v) // :_start(nullptr) // , _finish(nullptr) // , _endofstorage(nullptr) //{ // _start = new T[v.capacity()]; // memcpy(_start, v._start, sizeof(T) * size()); // _finish = _start + v.size(); // _endofstorage = _start + v.size();  //}  vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } }  void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }  vector<T>& operator=(vector<T> v) { swap(v); return *this; }

复制拷贝使用了copy-and-swap的典型实现

memcpy的拷贝问题

void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size());//memcpy delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n;  } }  void test_4() { bit::vector<string> v; v.push_back("111111"); v.push_back("222222"); v.push_back("333333"); v.push_back("444444"); v.push_back("555555");  for (auto& e : v) { cout << e << " "; } cout << endl;  }

如果扩容采用memcpy，此时新内存tmp与原指针指向同一块地址空间；

delete[]后旧内存被释放，源string被析构，此时tmp的string对象指针变成了悬空指针；

当再次对vector析构时，会导致对同一块内存二次释放，程序崩溃。

事实上：memcpy只是对源内存区域的数据原封不动复制到目标区域，逐字节拷贝，对于内置类型没有问题，但无法处理自定义类型

改进方案：

void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * size()); //memcpy逐字节拷贝，无法处理自定义类型  for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; }  delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n;  } }

调用赋值运算符重载，实现对string的深拷贝

完整实现

#pragma once #include<assert.h> #include<iostream>  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()) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { resize(n, val); }  vector() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { }  ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } }  //vector(const vector<T>& v) // :_start(nullptr) // , _finish(nullptr) // , _endofstorage(nullptr) //{ // _start = new T[v.capacity()]; // memcpy(_start, v._start, sizeof(T) * size()); // _finish = _start + v.size(); // _endofstorage = _start + v.size();  //}  vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } }  void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }  vector<T>& operator=(vector<T> v) { swap(v); return *this; }  void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * size());//memcpy逐字节拷贝，无法处理自定义类型  for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; }  delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n;  } }  size_t capacity() const { return _endofstorage - _start; }  size_t size() const { return _finish - _start; }  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 pop_back() { erase(--end()); }  void resize(size_t n, const T& val = T()) { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish != _start + n) { *_finish = val; ++_finish; } } }  void push_back(const T& x) { //if (_finish == _endofstorage) //{ // size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; // reserve(newcapacity); //} //*_finish = x; //++_finish;  auto it = insert(end(), x); }  iterator insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish);  if (_finish == _endofstorage) { size_t offset = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity);  pos = _start + offset; }  iterator end = _finish - 1;  while (end >= pos) { *(end + 1) = *end; end--; }  *pos = x; ++_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; }  private: iterator _start; iterator _finish; iterator _endofstorage; }; }

查看全文

http://www.jsqmd.com/news/669071/