文章目录
- 一、前言
- 二、构造函数
- 模拟实现构造函数调用不明确
- 三、基础接口
- 四、resize和reserve
- reserve中的深浅拷贝问题
- 五、尾插尾删
- 六、vector迭代器失效问题
- 七、模拟实现vector整体代码
一、前言
如何去模拟实现?我们可以看看vector的源码,抽离出底层结构:
template <class T, class Alloc = alloc>
class vector {
typedef T value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
protected:
iterator start;
iterator finish;
iterator end_of_storage;
}
这本质上与 T* a , size_t size, size_t capacity 是类似的:
其中
size = _finish - _start
capacity = _endofstorage - _start
二、构造函数
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
// 类模板的成员函数,还可以继续是函数模版
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
模拟实现构造函数调用不明确
不知道大家注意到没有,上面为啥重载了两个 vector(size_t n, const T& val = T()) 和 vector(int n, const T& val = T())?
1.问题描述
vector(size_t n, const T& val = T())//这里的形参用size_t就会引发这两个构造函数调用问题
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first++);
}
}
这里本意是想使用第一种构造方式,用3个6进行构造。编译器会根据形参调用最匹配的函数重载。
第一个构造函数的第一个形参是size_t,形参去匹配的话需要发生隐式类型转换。
但是这两个参数更匹配第二个构造函数(因为第二个模板可以为int,完全匹配),一旦走第二个构造函数,该构造函数内部是要对first进行解引用操作,所以编译器会报非法的间接寻址(解引用)错误。
2、解决调用不明确的方法
针对构造函数vector(size_t n, const T& val = T()),我们多重载一个vector(int n, const T& val = T())版本的构造函数即可解决该问题。
三、基础接口
1.empty和clear
empty
bool empty() const
{
return _finish == _start;
}
clear
void clear()
{
_finish = _start;//这里可不是置为nullptr哦
}
2.size和capacity
size
size_t size() const
{
return _finish - _start;
}
capacity
size_t capacity() const
{
return _endofstorage - _start;
}
3.[]和iterator
[]
提供const版本和非const版本:
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
iterator
同理普通迭代器和const迭代器版本,同理,范围for循环此时也是可以实现的:
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;
}
四、resize和reserve
resize
n个数据去初始化,这个n是多大,会造成什么影响?我们需要进行分类讨论:
void resize(size_t n, const T& val = T())//val给T类型的缺省值
{
if (n > capacity())//n大于capacity,要扩容
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else if (n > size())//n小于capacity但大于原size
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else//缩size的情况
{
_finish = _start + n;
}
}
resize的参数初始化值为T类型的构造,这里可不能直接初始化为0,要是T是自定义类型呢?是vector呢?所以这里如果T是vector的化调用的就是vector的构造函数。另外,这里还需要注意的一点是:构造vector的时候是匿名对象,匿名对象具有常性,不可修改所以要加上const修饰
所以,我们自然而然可以知道,对于内置类型比如int,都是有构造函数的。
reserve
reserve最大的问题就是深拷贝!开辟新空间进行赋值的时候如果直接使用memcpy是浅拷贝。
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
//size()需要先保存起来,后面_start会发生改变
size_t sz = size();
//为空不需要拷贝了
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
//memcpy(tmp, _start, sizeof(T) * size());//浅拷贝
//delete[] _start;
}
_start = tmp;
_finish = _start+sz;
_endofstorage = _start + n;
}
}
reserve中的深浅拷贝问题
1、reserve中浅拷贝发生原因
这句memcpy表面上把原来的数据全部拷贝到tmp里面了,但是,这只是按字节的拷贝,如果当前类型为vector<vector>等涉及深浅拷贝类型,将会发生浅拷贝。
2、浅拷贝发生的图解
memcpy会把vector<vector>,从_start位置开始,按字节进行拷贝。如图所示,拷贝的对象是4个vector,这是一种浅拷贝!
3、解决方法
void reserve(size_t n)
{
//扩容
if (n > capacity())
{
size_t oldSize = size();//先记录下size,后续解决finish失效
T* tmp = new T[n];
if (_start != nullptr)
{
//memcpy(tmp, _start, sizeof(T) * oldSize);//浅拷贝
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];//调用赋值运算符重载完成深拷贝
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;//异地扩容后_finish失效,需重新设定_finish
_end_of_storage = _start + n;
}
}
借助赋值运算符重载,完成深拷贝。
五、尾插尾删
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(_finish > _start);
--_finish;
}
六、vector迭代器失效问题
1.insert
//迭代器失效:扩容引起野指针问题
void insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(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 = val;
++_finish;
}
测试代码:
void Test3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = find(v.begin(), v.end(), 3);
if (it != v.end())
{
v.insert(it, 30);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
这是因为扩容导致pos失效了:
insert过程中发生扩容,导致it指向的空间实际上已经被释放,it指向已被释放的空间是野指针,造成了迭代器失效
所以,我们应该去更新pos,算出pos刚开始的相对位置,然后再去进行更新即可解决问题。但是此时外面调用insert的it仍然是失效的,因为是传值调用,形参改变不影响实参,可以通过返回值接收解决问题。(如果是传引用的话,只能传变量,而临时对象具有常性,不能调用,存在很多问题),所以直接用返回值解决。
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
//扩容会导致pos迭代器失效,需要更新
size_t len = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
void Test3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
v.insert(v.begin(), 0);
vector<int>::iterator it = find(v.begin(), v.end(), 3);
if (it != v.end())
{
v.insert(it, 30);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
2.erase
挪动数据进行覆盖即可
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
}
erase的pos也可能会导致pos失效,测试代码:
void Test6()
{
//删除所有偶数
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
上述代码在VS下,当erase(it)之后,it指向的位置发生改变,然后在++it的话,会出现问题,出现一些错误,造成迭代器失效。
我们最好统一认为失效了。
正确的erase:
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
测试代码:
void Test6()
{
//删除所有偶数
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
对于insert和erase存在迭代器失效的问题,当迭代器失效而来,我们就不要再去访问pos的位置了,要更新pos的位置,可通过返回值接收进行访问。
七、模拟实现vector整体代码
namespace fx
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector() = default;
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
// 类模板的成员函数,还可以继续是函数模版
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
void clear()
{
_finish = _start;
}
// v1 = v3
/*vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
clear();
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
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);
}
// v1 = v3
//vector& operator=(vector v)
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
void reserve(size_t n);
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
bool empty() const
{
return _start == _finish;
}
void push_back(const T& x)
{
// 扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
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;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
标签:finish,const,pos,C++,start,vector,模拟,size
From: https://blog.csdn.net/f_2789889770/article/details/142021603