✏️vector的模拟实现✏️
- 🌟初始结构
- 🌟构造函数
- 🌟拷贝构造
- 🌟赋值
- 🌟容量有关的操作
- ✨reserve
- ✨resize
- 💫size
- 💫capacity
- 🌟迭代器
- 🌟增删查改
- ✨push_back
- ✨pop_back
- ✨operator[]
- ✨迭代器失效问题
- ✨insert
- ✨erase
- 🌟reserve的memcpy浅拷贝问题
🌟初始结构
_start:指向首元素
_finsh:指向最后元素的下一个位置
_endofstorage:空间最后一个的下一个位置
namespace gpy
{
template <class T>
class vecrot
{
public:
typedef T* iterator;
~vector()
{
delete[] _start;
_start = _finsh = _endofstorage = nullptr;
}
private:
iterator _start;
iterator _finsh;
iterator _endofstorage;
};
}
🌟构造函数
这里就实现简单的无参构造函数
vector()
:_start(nullptr)
, _finsh(nullptr)
, _endofstorage(nullptr)
{}
🌟拷贝构造
//拷贝构造
vector(const vector<T>& v)
:_start(nullptr)
, _finsh(nullptr)
, _endofstorage(nullptr)
{
//提前开好空间再把数据尾插过来
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
🌟赋值
//赋值
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
🌟容量有关的操作
✨reserve
当我们插入数据空间不够时就可以调用reserve,如果我们知道需要用多大的空间时提前可以用reserve就会很方便。
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//开新的空间
size_t sz = size();//记录一下旧空间的size
if (_start)//_start为空就只开空间
{
memcpy(tmp, _start, sizeof(T)*sz);//把旧空间的数据拷贝到新空间
//释放旧空间
delete[] _start;
}
//更新新的空间
_start = tmp;
_finsh = _start + sz;
_endofstorage = _start + n;
}
}
✨resize
resize改变size,还是和string一样分情况。
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//开新的空间
size_t sz = size();//记录一下旧空间的size
if (_start)//_start为空就只开空间
{
memcpy(tmp, _start, sizeof(T)*sz);//把旧空间的数据拷贝到新空间
//释放旧空间
delete[] _start;
}
//更新新的空间
_start = tmp;
_finsh = _start + sz;
_endofstorage = _start + n;
}
}
💫size
获取数据个数,就是finsh-start
size_t size()const//让const对象也可以用
{
return _finsh - _start;
}
💫capacity
获取容量大小,和size相同的道理
size_t capacity()const//让const对象也可以用
{
return _endofstorage - _start;
}
🌟迭代器
//迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finsh;
}
//const对象使用
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finsh;
}
🌟增删查改
✨push_back
//尾插
void push_back(const T& x)
{
//if (_finsh == _endofstorage)
//{
// //增容，要考虑capacity为0的情况
// size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
插入数据
//*_finsh = x;
//++_finsh;
//insert实现好就可以复用
insert(_finsh,x);
}
✨pop_back
//尾删
void pop_back()
{
assert(!empty());//不为空才能删
--_finsh;
}
✨operator[]
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
✨迭代器失效问题
💥先说一个迭代器失效的问题，类似于野指针问题，直接上代码
std::vector<int> v2;
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
v2.push_back(5);
std::vector<int> ::iterator pos = find(v2.begin(),v2.end(),3);
if (pos != v2.end())
{
v2.insert(pos, 30);
}
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
*pos = 100;
此时代码已经报错，为什么呢？
💥当扩容后原来的空间就会释放掉此时pos就变成了野指针，在解引用程序就会报错，而如果是原地增容我们也认为是失效的，因为意义已经变了，我原本是指向2现在指向了20.
💥erase也会导致迭代器失效的问题，erase虽然没有导致野指针的问题但是意义变了，此时我们就要返回新的迭代器
✨insert
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start&&pos <= _finsh);//保证pos的有效性
if (_finsh == _endofstorage)
{
size_t n = pos - _start;//记录原来pos的位置
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + n;
}
//开始挪动数据
iterator end = _finsh - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finsh;
return pos;
}
✨erase
iterator erase(iterator pos)
{
assert(pos >= _start&&pos < _finsh);
iterator it = pos + 1;
while (it != _finsh)
{
*(it - 1) = *it;
++it;
}
--_finsh;
return pos;
}
上面有问题的代码就需要在接收一下pos就可以了。
std::vector<int> v2;
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
v2.push_back(5);
std::vector<int> ::iterator pos = find(v2.begin(),v2.end(),3);
if (pos != v2.end())
{
pos = v2.insert(pos, 30);
}
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
*pos = 100;
此时代码就可以跑起来了。
🌟reserve的memcpy浅拷贝问题
vector<string> v;
v.reserve(2);
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
每个vector种存string,而string会在堆上开空间，当delete旧空间，string的析构函数会释放掉原来的空间，新拷贝就指向的空间就被释放掉了，当vector调用析构函数就还会对刚才的空间在释放一次,
会对同一块空间释放2次。
正确写法：
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//开新的空间
size_t sz = size();//记录一下旧空间的size
if (_start)//_start为空就只开空间
{
for (size_t i = 0; i < size(); ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
//更新新的空间
_start = tmp;
_finsh = _start + sz;
_endofstorage = _start + n;
}
}