基本框架:
namespace xty
{
template<class T>
class vector
{
public:
typedef T* iterator;
///
//...
///
private:
iterator _strat; //起始位置
iterator _finish; //最后一个元素的下一个地址
iterator _end_of_storage; //容量的最后一个元素
};
}
vector的大致形状如下:黄色代表每天满的地方。
构造函数
使用初始化列表实现一个简单的无参构造函数。
//无参构造函数
vector()
:_finish(nullptr),
_start(nullptr),
_end_of_storage(nullptr)
{}
析构函数
记住要带[]即可。
~vector()
{
delete[] _start; //用带括号的
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
[]
T& operator[](size_t pos)
{
assert(pos < size());
return *(_start + pos);
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return *(_start + pos);
}
push_back
size()
size_t size() const
{
return _finish - _start;
}
capacity()
size_t capacity() const
{
return _end_of_storage - _start;
}
reserve()
因为push_back涉及到扩容函数,需要实现reserve()。
如下示例:
void reserve(size_t n)
{
if (n > capacity())
{
T* tem = new T[n];
if (_start)
{
memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
delete[] _start;
}
_start = tem;
_finish = _start + size(); //error
_end_of_storage = _start + n;
}
}
问题1:_finish赋值出错,出bug了,是因为size()函数,调用了空指针,导致报错。
改正:
因为delete之后,原数据就被清空了,所以可以提前保存一下size()的大小。
void reserve(size_t n)
{
if (n > capacity())
{
T* tem = new T[n];
const size_t sz = size(); //提前保存sz
if (_start)
{
memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
delete[] _start;
}
_start = tem;
_finish = _start + sz; //使用sz赋值
_end_of_storage = _start + n;
}
}
push_back()
逻辑比较简单,在vector的尾部添加一个val,就需要一些前置函数。
//尾插
void push_back(const T& val)
{
//满了扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
//插入数据
*_finish = val;
_finish++;
}
迭代器实现
该逻辑也比较简单,注意实现const的版本。
非const和const版本
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;
}
pop_back()
尾删。
bool empty()
{
return _start == _finish;
}
//尾删
void pop_back()
{
assert(!empty());
_finish--;
}
resize()
和string逻辑差不多。
void resize(size_t n, const T& val = T())
{
//一样大,直接返回
if (n == size())
{
return;
}
if (n<size()) //小于直接修改_finish
{
while (n != size())
{
--_finish;
}
}
else
{
if (n > capacity()) //大于容量先扩容
{
reserve(n);
}
while (n != size())
{
push_back(val);
}
}
}
优化:该函数多次调用push_back()使用while,效率低。
void resize(size_t n, const T& val = T())
{
if (n == size())
{
return;
}
if (n < size())
{
_finish = _start + n; //直接移动_finish
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n) //使用指针操作,减少调用
{
*_finish = val;
_finish++;
}
}
}
insert()***重点
传入迭代器的位置,插入一个元素。
void insert(iterator pos ,const T& val)
{
//检测pos位置是否合法
assert(pos >= _start);
assert(pos <= _finish);
// 满了需要扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
//从后往前移动
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
*pos = val; //在该位置赋值
_finish++;
}
算法问题1:会造成迭代器失效,迭代器失效,实际就是迭代器底层对应指针所指[空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
该程序正常来说没有问题,当出现扩容的时候,reserve()会删除原来的空间,去申请新的空间,因此会导致pos指向的那段空间被释放掉,pos变成野指针。
改正:记录插入的相对位置,扩容后根据相对位置更新pos的值。
void insert(iterator pos, const T& val)
{
//检测pos位置是否合法
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;
while (end > pos)
{
*end = *(end - 1);
end--;
}
*pos = val; //在该位置赋值
_finish++;
}
算法问题2:执行insert后,如果扩容,pos位置已经改变了,而函数外面的pos因为是值传递,并没有修改,同样导致了野指针的问题。(迭代器再一次失效!)
解决办法:
- pos传引用可以吗?
不可以。如下图:如果传入v.begin(),会报错。因为begin()是传值返回,传值返回有一个临时变量,而临时变量具有常性,不能被修改,insert里面就不能修改了!
- 通过返回值解决可以吗?
可以,我们可以利用insert返回值的特性,来更新pos防止失效!
如下图:这样就解决问题了。
最终版本:
iterator insert(iterator pos, const T& val)
{
//检测pos位置是否合法
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;
while (end > pos)
{
*end = *(end - 1);
end--;
}
*pos = val; //在该位置赋值
_finish++;
return pos;
}
总结:使用insert后,我们默认迭代器失效!因为我们不知道何时执行扩容操作,因此需要重新对pos赋值,防止这类情况发生!
erase()***重点
指定位置执行删除操作。
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
auto end = pos + 1;
while (end < _finish)
{
//后给前,从前往后
*(end - 1) = *end;
end++;
}
_finish--;
}
问题1:erase会导致迭代器失效?
==会导致!==如果删除最后一个位置,最后一个位置就变成了空位置,导致pos也指向了不该指向的位置。因此,erase()执行过后,应该重新给pos赋值再使用!
最终版本:添加返回值。
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
auto end = pos + 1;
while (end < _finish)
{
//后给前,从前往后
*(end - 1) = *end;
end++;
}
_finish--;
return pos;
}
最后给大家一个例子自己感受:
该例子在VS2019会报错
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
return 0;
}
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
++it;
}
return 0;
}
再谈构造函数!
这次实现一个可以规定数量和内容的构造函数。
//正常实现
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
size_t len = n;
while (n--)
{
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);
++first;
}
}
当我们满心欢喜的实现好这两个构造函数后,想要测试一下。结果报错了。
输入: vector vx(10,5);
这是为什么呢?因为10,5都被编译器认为是int类型,而编译器在函数重载时,会自动调用最合适的,而它认为第二个函数更适合自己(),因此解引用的时候产生非法间接寻址!
因此我们需要再次实现一个int型的函数重载!
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
size_t len = n;
while (len--)
{
push_back(val);
}
}
迭代器构造还支持以下方法:
int a[] = { 1, 2, 3 };
vector<int> v4(a, a + 3);
for (auto e : v4)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
拷贝构造函数****(重点)
如果我们不自己实现拷贝构造函数,编译器就会默认生成一个,但是编译器默认生成的是浅拷贝,不可以。
//拷贝构造
vector(const vector<T>& v)
{
//扩容
reserve(v.capacity());
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
}
现在我们写完这个函数的拷贝构造之后,看看是否有问题:
提前告诉大家,这个程序会崩溃,因为memcpy()实现的是浅拷贝,他仅仅会拷贝v3的首尾指针,并不会开一个新的空间去存储相应的字符串。所以,程序结束时,调用析构函数,会连续析构两次!
**解决办法:**不适用memcpy()自己实现深拷贝,使用‘=’即可实现,因为string赋值操作就是深拷贝,string的赋值,就会先开空间,再拷贝!
//拷贝构造
vector(const vector<T>& v)
{
//扩容
reserve(v.capacity());
//memcpy(_start, v._start, sizeof(T) * v.size());
for (size_t i = 0; i <v.size(); i++)
{
_start[i] = v._start[i]; //变成string对象的拷贝
}
_finish = _start + v.size();
}
但是reverse()也会产生这个浅拷贝的问题,因此将reserve也应该改成深拷贝。
void reserve(size_t n)
{
if (n > capacity())
{
T* tem = new T[n];
const size_t sz = size(); //提前保存sz
if (_start)
{
//memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
for (size_t i = 0; i < size(); i++)
{
tem[i] = _start[i];
}
delete[] _start;
}
_start = tem;
_finish = _start + sz; //使用sz赋值
_end_of_storage = _start + n;
}
}
这样vector的问题就解决了。但是vector<vector<int>>还有问题!!!请看赋值重载的部分。
=运算符重载***(重点)
这里暴露了一个问题,就是虽然外面的vector是深拷贝,但是里面的vector是浅拷贝,是由于没有写vector的赋值重载,再补充一个赋值重载即可!
vector<T>& operator=(vector<T> v)
{
swap(v);
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);
}
文章来源:https://www.toymoban.com/news/detail-743632.html
运算符重载和拷贝构造这里写的不太详细,后续还会补充!文章来源地址https://www.toymoban.com/news/detail-743632.html
到了这里,关于vector类模拟实现(c++)(学习笔记)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!