vector会使用之后我们来模拟实现一下,通过对vector的模拟实现,我们来说一下迭代器失效问题。
1.准备工作
在头文件vector.h里声明和实现函数,然后在test.cpp里测试代码的正确性。
在vector.h中用命名空间分隔一下,因为c++库里面也有vector,避免冲突。vector.h里面写一些会用到的头文件,vector的成员变量类型都是T*,为了和vector源码保持一致,我们也把T*换个名字,换成iterator,然后定义成员变量。
namespace lyj
{
template<class T>
class vector
{
public:
typedef T* iterator;
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
2.size、capacity、reserve
全都在vector.h的vector类里面声明和实现,目前不做声明和定义分离。
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
void reserve(size_t n)
{
if (n > capacity()) //n大于capacity扩容
{
T* t = new T[n];//开辟新空间
memcpy(t, _start, size * sizeof(T));//拷贝旧空间的数据到新空间
delet[] _start; //释放旧空间
_start = t; //指向新空间
_finish = _start + size();//更新数据
_end_of_storage = _start + n;//更新数据
}
//其他不变
}
3.operator[]、push_back、pop_back、empty
全都在vector.h的vector类里面声明和实现,目前不做声明和定义分离。
//普通版本
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
//const版本
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
//尾插
void push_back(const T& x)
{
if (_finish == _end_of_storage)//空间不够
{
reserve(capacity() == 0 ? 4 : capacity() * 2);//2倍扩
}
*_finish = x;
++_finish;
}
//判空
bool empty() const
{
return _start == _finish;
}
//尾删
void pop_back()
{
assert(!empty());
--_finish;
}
在test.cpp中对前面的所有代码进行测试。
#include "vector.h"
namespace lyj
{
void test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
}
int main()
{
lyj::test1();
return 0;
}
运行发现程序崩溃了。
因为我们前面的reserve逻辑有问题。
所以_finish 不是我们想要的值。
解决方法1:先更新_finish。
void reserve(size_t n)
{
if (n > capacity()) //n大于capacity扩容
{
T* t = new T[n];//开辟新空间
memcpy(t, _start, size() * sizeof(T));//拷贝旧空间的数据到新空间
delete[] _start; //释放旧空间
_finish = t + size();//先更新_finish的数据
_start = t; //再指向新空间
_end_of_storage = _start + n;//更新数据
}
//其他不变
}
解决方法2:用old_size存值。
void reserve(size_t n)
{
if (n > capacity()) //n大于capacity扩容
{
size_t old_size = size();//存值
T* t = new T[n];//开辟新空间
memcpy(t, _start, size() * sizeof(T));//拷贝旧空间的数据到新空间
delete[] _start; //释放旧空间
_start = t; //指向新空间
_finish = t + old_size;//用old_size更新数据
_end_of_storage = _start + n;//更新数据
}
//其他不变
}
再运行代码,就可以通过了。
4.迭代器和范围for
4.1 普通正向迭代器
全都在vector.h的vector类里面声明和实现,目前不做声明和定义分离。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
在test.cpp中进行测试。
void test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
}
4.2 普通范围for
支持迭代器就支持了范围for。
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
4.3 const迭代器
const迭代器就要用const的iterator,所以我们typedef一个const_iterator,原类型是const T*。
typedef const T* const_iterator;
const迭代器的实现就是把普通正向迭代器返回值类型换一下。
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
当迭代器换成const迭代器后,范围for也要是const的。
在test.cpp中进行测试。
void test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
5.拓展知识
我们把迭代器和范围for打印数据单独写成一个函数。
void vector_print(const vector<int>& v)
{
vector<int>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
但是我们写的这个函数只能打印vector<int>类型的数据,我如果想打印vector<double>呢?
有人肯定想到了,写成函数模板。
template<class T>
void vector_print(const vector<T>& v)
{
vector<T>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
这样想打印什么就打印什么。
但是这样写,编译器会编译报错,因为:没有实例化的类模板里面取东西,编译器不能区分这里的const_iterator是类型还是静态成员变量。
解决方法1:在vector<T>::const_iterator it = v.begin();这句代码前面加上typename,就是我们告诉编译器,这里是类型。
解决方法2:类型直接写成auto。
6.insert和迭代器失效问题
在vector.h的vector类里面声明和实现,insert代码如下。
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start; //记录距离
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新pos
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
}
6.1 失效情况1
按照我们写string的insert的思路写vector的insert。
void insert(iterator pos, const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
}
在test.cpp中进行测试。
void test2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.vector_print(v);
v.insert(v.begin() + 2, 30);
v.vector_print(v);
}
当我们已经扩容好的时候,这个程序是没问题的。但是如果空间不够,我们插入数据时正好要扩容呢?程序会出现崩溃。
原因如下。
此时的pos已经找不到了,类似野指针。这就是一个最基础的迭代器失效问题。
解决方法就是我们先记录pos到start的位置距离,在扩容的时候更新pos,代码如下。
void insert(iterator pos, const T& x)
{
if (_finish == _end_of_storage)
{
size_t len = pos - _start; //记录距离
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新pos
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
}
6.2 find
其实vector并没有像string那样实现find接口,如果我们想在vector用find,就要用算法库里面的find。
这个find是个模板,所有的容器都可以使用,这也体现了封装的特点。这个函数在first和last-1的区间找,找到了就返回下标,没找到就返回last。
比如说我们要找2,用法如下。
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);
然后呢在2的前面插入一个40.
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);
if (pos != v.end())
{
v.insert(pos, 40);
}
v.vector_print(v);
6.3 失效情况2
访问pos,让pos位置的值加1。
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);
if (pos != v.end())
{
v.insert(pos, 40);
*pos += 1; //pos位置的值加1
}
v.vector_print(v);
pos地方的值毫无变化。 虽然pos在insert内部更新了,但是这种在外部访问的情况下,pos是局部变量,出了作用域就被销毁了,其实就是形参的改变不影响实参。参数pos加&是行不通的,因为这样就不支持别的迭代器了。
insert之后,pos已经失效了,前面画过图,所以,insert之后pos失效,不要访问。
insert改写
如果我们非要访问,insert的写法就要发生变化。如下。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start; //记录距离
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新pos
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
return pos; //返回插入的位置
}
解决方法
然后我们记录pos的位置,再访问pos。
void test3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto pos = find(v.begin(), v.end(), 2);
if (pos != v.end())
{
pos = v.insert(pos, 40);
*pos += 1; //pos位置的值加1
}
v.vector_print(v);
}
所以insert之后pos失效,不要直接访问,要访问就要更新这个失效的迭代器。
6.4 失效情况3
以前面的pos为例,pos原本指向的是2,我们插入一个数据之后,pos指向了新插入的那个数据。
这也是一种迭代器失效的情况。前两种失效情况我们可以理解为类似野指针,这种失效情况就是位置的意义已经变了。 所以insert后我们认为迭代器也失效了,所以不要访问。
如果使用vector,在vs下上述情况去访问pos,是会直接报错的,Linux下不会,这要看编译器。
7.erase和迭代器失效问题
7.1 erase
在vector.h的vector类里面声明和实现。
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
_finish--;
}
在test.cpp中进行测试。比如我们要删除所有偶数。
void test4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.vector_print(v);
vector<int>::iterator i = v.begin();
while (i != v.end())
{
if (*i % 2 == 0)
{
v.erase(i);
}
++i;
}
v.vector_print(v);
}
看起来成功了,我们换一个测试样例,换成123445。
没删干净。 再换一个样例1234。
程序崩溃。
7.2迭代器失效问题
erase这里的迭代器失效和前面的失效情况一样,此时的i已经不是原来的数据了,就是失效了。如果一定要访问,更新一下在访问。
erase改写
所以我们这里的erase要有返回值,返回被删除元素的下一个元素。
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
_finish--;
return pos;
}
在test.cpp中进行测试。
void test4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.vector_print(v);
vector<int>::iterator i = v.begin();
while (i != v.end())
{
if (*i % 2 == 0)
{
i = v.erase(i);//erase返回的是被删除数据的下一个数据
}
else
++i;
}
v.vector_print(v);
}
都能正确处理。
8.resize
先回顾一下std里面中resize的结构。
在vector.h的vector类里面声明和实现。
这里的value_type其实就是模板参数T。所以我们在模拟实现resize的时候参数如下。
void resize(size_t n, T val = T())
{
}
这里T val = T()就是先通过后面的T的默认构造去构造一个匿名对象,然后再拷贝构造给前面的val,自定义类型要缺省的话,就是像这样,给相应的默认构造。当然这里默认构造+拷贝构造我们说过编译器可能会做优化,直接就是一个构造。
拓展
但是,但是,如果T不是自定义类型呢?我们说过,内置类型没有构造这样的概念。针对这一情况,内置类型也有了构造函数的概念。
int i = int();//初始化为0
iny j = int(1);//初始化为1
int k(2); //初始化为2
通过前面对resize的了解,我们知道,resize会出现三种情况。如下。
如果忘记了,请看【C++】vector使用详解_vector c++ 用法-CSDN博客 5.resize 。
我们模拟实现的时候也分两个情况就可以了,n<size和其他情况。
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);//reserve内部会对n判断
while (_finish < _start + n)
{
_finish = val;
++_finish;
}
}
}
在test.cpp中进行测试。
void test5()
{
vector<int> v;
v.resize(6, 5);
v.vector_print(v);
}
9.构造函数和析构函数
9.1 析构函数
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
9.2 构造函数
//vector() //默认构造
//{}
//C++11支持,强制生成默认构造
vector() = default; //默认构造
vector(const vector<T>& v)//拷贝构造
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
10.swap、clear和operator=
在vector.h的vector类里面声明和实现。
10.1 传统写法
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
void clear()
{
_finish = _start;
}
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
clear();
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
return *this;
}
上面写的是传统写法。
在test.cpp中进行测试一下传统写法。
vector<int> v1, v2;
v1.resize(5, 1);
v1.vector_print(v1);
v2.resize(5, 2);
v2.vector_print(v2);
v2 = v1;
v2.vector_print(v2);
10.2 现代写法
现代写法的具体内容在【C++拓展】深拷贝的传统写法vs现代写法,你更喜欢哪个?-CSDN博客
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
测试用例和上面一样。
vector模拟实现大概结构以及迭代器失效问题就介绍完了,拜拜~