vector
一、vector的注意事项
1. [] 和 at() 的越界访问
vector<int> v1{ 1,2,3,4 };
//v1[4] = 5; //越界直接结束,assert判断
try
{
v1.at(4) = 5; //抛异常
}
catch (...)
{
cout << "beyond" << endl; //输出beyond
}
2.迭代器失效问题
简单来说就是在迭代器创建后 使用了reverse,resize,insert,push_back等导致的增容 导致迭代器仍然指向已经被释放的旧空间
一个应对迭代器失效的过程
//删除容器中所有的偶数
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
//然后该怎么++it?
++it; //此时会报错,为什么?
//erase删除一个数据后,其他数据向前移动,移动后其实it已经指向我们想要遍历的下一个元素
//此时再++it就会导致错过部分数据
else
{
++it; //那么这样处理可以么?
//Linux环境下这样可以达到目的,但是vs编译环境自动检查且较为严格,仍然报错
}
}
//正确做法
vector<int>::iterator it2 = v.begin();
while (it2 != v.end())
{
if (*it2 % 2 == 0)
it2 = v.erase(it2); //正确做法 erase会返回删除的it的下一个位置的迭代器
else
++it2;
}
二、vector的模拟实现
有以下要点:
reserve中浅拷贝memmove问题 新型拷贝构造和重载赋值符写法 insert时的迭代器失效
namespace 9TSe
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
//v2(v1)
//vector(const vector<T>& v)
//{
// _start = new T[v.capacity()]; //开辟新空间
// _finish = _start;
// _endofstorage = _start + capacity();
// for (size_t i = 0; i < v.size(); ++i)
// {
// *_finish = v[i];
// ++_finish;
// }
//}
//拷贝构造的另一种方法
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
for (auto& e : v)
{
reserve(v.capacity());
push_back(e);
}
}
//vector<T>& operator=(const vector<T>& v)
//{
// if (*this != &v) //防止自己赋值给自己
// {
// delete[] _start; //s1 = s2 s1有自己的空间,先释放
// _start = new T[v.capacity()];
// memcpy(_start, v._start, sizeof(T) * v.size());
// }
// return *this;
//}
//重载赋值运算符简便写法
void swap(vector<T>& v)
{
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> v)
{
if (*this != &v)
swap(v); //这里不用库内自带的swap是因为,其会生成三个深拷贝,有很大的代价
return *this;
}
~vector()
{
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) //这里的用意是防止_start为空指针时扩容,会导致memcpy出错(memcpy内不能存在空指针)
{
//memcpy(tmp, _start, sizeof(T) * size()); //这个memcpy是浅拷贝,当T为string时,会导致指针指向同一位置,释放两次同一空间
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = tmp + sz; //如果这里赋予 tmp + size() 会出错
//sz的计算方式是_finish-_start
//_start已经指向新空间了,finish还指向旧空间
_endofstorage = tmp + n;//这里如果赋予tmp + capacity() 也会出错,与上同理
}
}
void resize(size_t n, const T& v = T()) //这里的T()为T类型的默认缺省值,有int() double() 等都有
//int() double()等内置类型,只是专门创建了此形式的东西
//string ,vector 是调用构造函数
{
if (n < size()) //缩容
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish < _start + n)
{
*_finish = v;
++_finish;
}
}
}
void push_back(const T& x)
{
if (_finish == _endofstorage) //扩容
{
size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
void insert(iterator pos, const T& v) //这里会有迭代器失效问题
{
assert(pos <= _finish);
if (_finish == _endofstorage)//pos会扩容后失效
{
size_t n = pos - _start; //因此要记录之间的距离,以明确新pos指针指向的位置
size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
reserve(newcapacity);
pos = _start + n; //设置新pos
}
iterator end = _finish - 1;
while (end >= pos) //移动数据
{
*(end + 1) = *end;
end--;
}
*pos = v;
++_finish;
}
iterator erase(iterator pos)
{
assert(pos < _finish&& _start != _finish);
iterator it = pos;
while (it < _finish)
{
*it = *(it + 1);
++it;
}
_finish--;
return pos;
}
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _endofstorage - _start;
}
iterator end()
{
return _finish;
}
iterator begin()
{
return _start;
}
const_iterator end()const
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
T& operator[](size_t i)
{
assert(i < size());
return *(_start + i);
}
const T& operator[](size_t i)const
{
assert(i < size());
return *(_start + i);
}
void pop_back()
{
assert(_start < _finish);
_finish--;
}
private:
iterator _start;
iterator _finish; //这个指针指向的是最后一个数据的下一个数据的位置
iterator _endofstorage;
};
}