👀樊梓慕:个人主页
🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》
🌝每一个不曾起舞的日子,都是对生命的辜负
前言
本篇文章旨在记录博主在模拟实现vector容器中遇到的一些问题,都是一些需要注意的细节问题,希望与大家共勉。
欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。
=========================================================================文章来源地址https://www.toymoban.com/news/detail-796180.html
GITEE相关代码:🌟fanfei_c的仓库🌟
=========================================================================
1.迭代器失效问题
迭代器失效可以大致总结为:
之前我们说迭代器的底层可以理解为指针,那么迭代器失效其实就是『 底层指针的指向发生了改变,而迭代器没有』,这就会导致使用迭代器时报错或者出现错误数据。
并且迭代器失效一般具有下面的特点:
- 一般发生在需要扩容时,比如resize、reserve、insert、assign、push_back;
- 解决方案一般为将迭代器重新赋值,所以我们查看STL-vector的底层源码会发现insert等函数实现时会有返回值,这个返回值就是让我们在使用时,将迭代器重新赋值用的(博主也模拟实现了下供大家参考);
问题剖析(以reserve和insert举例说明)
void reserve(size_t n)
{
if (n > capacity())
{
size_t old = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, old * sizeof(T));
//delete[] _start;
for (size_t i = 0; i < old; i++)//解决方案
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_endOfStorage = _start + n;
}
}
可以看到我注释掉的代码,在最开始可能你会利用memcpy来简化代码,一步到位非常方便,但这就引发了一些意想不到的后果:『 迭代器失效』。
假设vector中存储的为string类:
用memcpy会导致:如果调用了reserve函数,执行到memcpy,memcpy实际为一种『 浅拷贝行为』
『 delete[]会调用析构然后释放空间』
执行过memcpy后,如果执行delete[] _start就会调用析构函数,然后string的析构导致_ str成为野指针, 进而导致vector的迭代器_start失效。
同样这个问题到insert的模拟实现处也存在,因为利用了memmove,比如:
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endOfStorage)
{
size_t len = pos - _start;//保存长度
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
pos = _start + len;//扩容后更新pos的位置,否则pos依旧指向被释放的旧空间
}
//memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
iterator end = _finish - 1;//解决方案
while (end > pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
解决memcpy、memmove浅拷贝行为导致迭代器失效的问题:
- 如代码所示,利用重载的赋值操作符就可以避免这一问题,因为赋值是一种『 深拷贝行为』。
以上是模拟实现过程中解决的迭代器时效问题。
那么在应用中,我们可以利用erase、insert的返回值将迭代器重新赋值,防止迭代器失效。
it = s.begin();
while (it != s.end())
{
it = s.erase(it);
// 按照下面方式写,运行时程序会崩溃,因为erase(it)之后
// it位置的迭代器就失效了
// s.erase(it);
++it;
}
另一种解决方案是可以利用『 引用计数』的方式,这里我就不多赘述了,不了解的小伙伴可以自行百度。
2.构造函数重载导致歧义(迭代器区间构造)
迭代器区间构造是一种十分精妙的构造方式,它可以将任意类型(只要支持迭代器)初始化给vector,参数只需要传递两个迭代器即可,比如:
template <class InputIterator>//泛型迭代器
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
//同类型构造
vector<int> v2(v1.begin(), v1.end());
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
//不同类型构造
vector<int> v3(lt.begin(), lt.end());
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
//甚至是数组
int a[] = { 100, 200, 300 };//底层物理空间连续,天然的迭代器-指针
vector<int> v4(a, a+3); //指向连续物理地址空间的指针就是天然的迭代器,符合迭代器要求
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
但vector中有某类构造函数是这样的:
vector(size_t n, const T& val = T())//将容器初始化为n个val
{
resize(n, val);
}
如果你写了这样的代码:
void test_vector()
{
vector<string> v1(5, "1111");//ok
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v2(5, 1);//err
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
这就会引发报错:
问题剖析
原因就是你的程序可能没有按你的本意走,你的本意是想『 将v2初始化为5个1』。
可是编译器会将5和1识别为迭代器,因为5和1的类型相同,不需要发生类型转换。
为什么不会识别为(size_t n,const T& val = T())呢,很明显编译器也不想发生类型转换,size_t为unsigned char,另一个参数为const T&(这里为int),需要发生类型转转换才可以匹配。
所以为了解决这一问题,我们需要再额外重载一个:
vector(size_t n, const T& val = T())//将容器初始化为n个val
{
resize(n, val);
}
vector(int n, const T& val = T())//为了解决两个参数都为int,会自动匹配迭代器区间初始化函数导致报错
{
resize(n, val);
}
虽然看起来好像不太高级,但是实际上STL也是这么做的。
3.vector模拟实现源码
template<class T>
class vector
{
public:
//Vector的迭代器是一个原生指针
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;
}
// construct and destroy
vector()
{}
vector(const vector<T>& v)
{
//传统写法
/*_start = new T(v.capacity());
memcpy(_start, v._start, v.size() * sizeof(T));
_finish = _start + v.size();
_endOfStorage = _start + v.capacity();*/
//现代写法
reserve(v.capacity());
for (const 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())//如果传参两个int,会导致不匹配该函数而匹配迭代器区间初始化函数
{
resize(n, val);
}
vector(int n, const T& val = T())//为了解决两个参数都为int,会自动匹配迭代器区间初始化函数导致报错
{
resize(n, val);
}
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
// capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, old * sizeof(T));//用memcpy会导致模板为string类时,如果vector需要扩容,此时memcpy实际为一种“浅拷贝行为”,string成员_str会因为delete[] _start成为野指针
//delete[] _start;//delete[]会调用析构然后释放空间
//同样这个问题到insert的模拟实现处也存在,因为利用了memmove
for (size_t i = 0; i < old; i++)//解决方案 另一种解决方案是可以利用“引用计数”
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n > size())
{
if (n > capacity())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
else
_finish = _start + n;
}
///access///
T& operator[](size_t pos)
{
return _start + pos;
}
const T& operator[](size_t pos)const
{
return _start + pos;
}
///modify/
void push_back(const T& x)
{
//1.判断容量
if (_finish == _endOfStorage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
//2.尾插
*_finish = x;
++_finish;
}
void pop_back()
{
assert(size() > 0);
--_finish;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endOfStorage)
{
size_t len = pos - _start;//保存长度
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
pos = _start + len;//扩容后更新pos的位置,否则pos依旧指向被释放的旧空间
}
//memmove(pos + 1, pos, (_finish - pos) * sizeof(T));//memmove是一种浅拷贝行为,可能会造成模板为string类时,野指针的问题
iterator end = _finish - 1;
while (end > pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)//未测试
{
assert(size() > 0);
assert(pos >= _start && pos < _finish);
//memmove(pos , pos+1, (_finish - pos) * sizeof(T));//memmove是一种浅拷贝行为,可能会造成模板为string类时,野指针的问题
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
private:
iterator _start = nullptr; // 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾
iterator _endOfStorage = nullptr; // 指向存储容量的尾
};
以上就是本篇文章的全部内容。
模拟实现的意义就是『 让我们更好的使用』,像迭代器失效、构造函数重载-迭代器区间构造导致歧义等问题,只有我们模拟实现过,才能更深切得体会到为什么STL库的设计者要这么写,这么写的意义是什么。
=========================================================================
如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容
🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏+关注 ~🌟文章来源:https://www.toymoban.com/news/detail-796180.html
=========================================================================
到了这里,关于【C++】vector模拟实现过程中值得注意的点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!