【C++】vector模拟实现+迭代器失效
vector模拟实现
- 成员变量定义
- 默认成员函数
- 构造函数
- 迭代器
- 范围for、对象类型匹配原则
- 容量操作
- size
- empty
- capacity
- reserve
- 成员变量未更新
- memcpy值拷贝
- resize
- 内置类型的构造函数
- 数据访问
- front
- back
- operator[ ]
- 数据修改操作
- push_back
- pop_back
- swap
- clear
- insert
- pos位置未更新
- 无返回值
- erase
- 无返回值
- 迭代器失效
- 定义
- insert导致的迭代器失效
- erase导致的迭代器失效
- 删除vector中的奇数
- 非法的间接寻址
铁汁们,今天给大家分享一篇vector模拟实现 + 迭代器失效,来吧,开造⛳️
成员变量定义
- 指向最后一个空间的下一个位置
???? iterator _endofstorage
- 指向存储第一个有效数据空间的位置
???? iterator _start
- 指向存储最后一个有效数据空间的下一个位置
???? iterator _finish
- 在成员变量声明处给缺省值,实质上是将缺省值给了初始化列表。
- 在创建一个新的对象时,都需要先走初始化列表完成初始化,在走构造函数。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<assert.h>
using namespace std;
template<class T>
class vector {
private:
iterator _start = nullptr; //起始位置
iterator _finish = nullptr; //有效数据的结束位置
iterator _endofstorage = nullptr; //容量的结束位置
};
默认成员函数
构造函数
????vector( ) { } ;
- 功能:构造无参的对象
vector() {}; //无参构造
????vector(size_t n, const T& val = T( ) ) ;
- 功能:构造含n个val值的对象
vector(size_t n, const T& val = T()) //用n个val值构造
{
resize(n, val);
}
????vector( InputIterator first, InputIterator last ) ;
- 功能:构造与[first, last)范围一样多元素的对象
template<class InputIterator> // 注意: 模板内可以在嵌套模板
vector(InputIterator first, InputIterator last) //用迭代区间进行构造
{ //泛型编程,函数模板,不是只适用于某个容器的的迭代器,适用于所有容器的的迭代器
while (first != last)
{
push_back(*first);
first++;
}
}
????Tips:模板内可以嵌套其他模板。
迭代器
template<class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
}
???? Tips:指向连续物理空间的指针是天然的迭代器。
????iterator begin( ) ;
- 功能:返回指向第一个元素的位置。
iterator begin() //迭代器所指向的空间内的值 “既可读又可写”
{ //只适用于const对象(权限可以平移)、不适用于非const对象(权限不可以放大)
return _start; //vector第一个元素所在的位置(指针)
}
????Tips : const_iterator 修饰的是迭代器所指向的元素不能被修改,而迭代器本身可以被修改。const修饰this指针,表示在该成员函数中成员变量不允许被修改,此处const的用法只能用于类中的成员函数。
????iterator end( ) ;
- 功能:返回指向最后一个元素的下一个位置。
iterator end()
{
return _finish; //vector最后一个元素后面所在的位置(指针)
}
????const_iterator begin( )const ;
const_iterator begin()const //迭代器所指向的空间内的值 “只可不可写”
{
return _start; //既适用于const对象(权限可以平移)、又适用于非const对象(权限可以缩小)
}
????const_iterator end( )const ;
const_iterator end()const
{
return _finish;
}
范围for、对象类型匹配原则
const vector<int> v(5, 2);
for (auto& e : v)
{
cout << e << ' ';
}
cout << endl;
-
只要容器支持迭代器,就支持用范围for来访问, 原因:范围for的底层实现为迭代器。
-
用范围for访问对象中的元素,对象类型不同,范围for底层调用的迭代器接口不同。
容量操作
size
????size_t size( )const ;
- 功能:计算元素的总个数
size_t size()const //有效元素总个数
{
return _finish - _start;
}
empty
????bool empty( )const ;
- 功能:判断vector是否为空,为空,则返回true,不为空,则返回false。
bool empty()const //判断是否为空, 为空,则返回true,不为空,则返回false
{
return size() == 0;
}
vector<string> v1;
v1.push_back("zhangsan");
cout << v1.empty() << endl;
vector<int> v2;
cout << v2.empty() << endl;
capacity
????size_t capacity( )const ;
- 功能:获得当前分配给vector存储空间的大小。
size_t capacity()const //容量的大小
{
return _endofstorage - _start;
}
reserve
????void reserve(size_t n) ;
- 功能:使得vector容器存储空间的大小为n。
void reserve(size_t n) //开空间(扩容)
{
if (n > capacity()) //此处在判断:1.自己直接调用reserve,2.其他接口间接调用reserve
{
T* tmp = new T[n]; //扩容 new:开空间+构造函数,完成初始化
size_t old = size(); // 注意 :因为new[]会开辟新的空间
if (_start) //拷贝旧空间中的值
{
for (int i = 0; i < old; i++) //vector底层物理空间连续
tmp[i] = _start[i] ; // 若为string,则调用string的赋值重载函数(深拷贝)
delete[] _start; //delete:析构函数+释放空间
}
//更新成员变量
_start = tmp;
_finish = _start + old; //
_endofstorage = _start + n; //
}
}
成员变量未更新
void reserve(size_t n) //开空间(扩容)
{
if (n > capacity()) //此处在判断:1.自己直接调用reserve,2.其他接口间接调用reserve
{
T* tmp = new T[n]; //扩容 new:开空间+构造函数,完成初始化
if (_start) //拷贝旧空间中的值
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start; //delete:析构函数+释放空间
}
//更新成员变量
_start = tmp;
_finish = _start + size();
_endofstorage = _start + capacity();
}
}
memcpy值拷贝
void reserve(size_t n) //开空间(扩容)
{
if (n > capacity()) //此处在判断:1.自己直接调用reserve,2.其他接口间接调用reserve
{
T* tmp = new T[n]; //扩容 new:开空间+构造函数,完成初始化
size_t old = size(); // 注意 :因为new[]会开辟新的空间
if (_start) //拷贝旧空间中的值
{
memcpy(tmp, _start, sizeof(T) * old);
delete[] _start; //delete:析构函数+释放空间
}
//更新成员变量
_start = tmp;
_finish = _start + old; //
_endofstorage = _start + n; //
}
}
resize
????void resize(size_t n, const typename& val = typename( ) ) ;
- 功能:调整vector容器的大小,使其内元素个数变为n。
void resize(size_t n, const T& val = T()) //开空间+初始化
{
if (n > size()) //插入数据 -》 n > capacity:扩容+插入 size < n <capacity:插入
{
reserve(n); // n > capacity
for(int i = size(); i < n; i++) //从size位置处向后插入
push_back(val);
}
else //n < size:尾删
{
_finish = _start + n;
}
}
vector<int> v2;
v2.push_back(2);
v2.push_back(2);
v2.push_back(2);
v2.push_back(2);
v2.push_back(2);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
v2.resize(7, 1);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
v2.resize(12);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
v2.resize(3);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
内置类型的构造函数
int a = int();
cout << a << endl;
int b = int(5);
cout << b << endl;
????Tips :初始化处默认给缺省值,缺省值为无参构造函数,自定义类型会去调它自己的默认构造函数,c++11为了兼容模板,使得内置类型也有构造函数,内置类型得无参构造函数初始化为0,eg:int val = int(), val = 0、double val = double(),val = 0.0,int* val = int*() , val = nullptr、char val = char(), val = ‘\0’。
数据访问
front
????T& front( ) ;
- 功能:获取第一个有效元素
T& front() //获取第一个有效元素
{
assert(size() > 0); //断言,确保是否有数据
return *_start;
}
back
????T& back( ) ;
- 功能:获取最后一个有效元素
T& back() //获取最后一个有效元素
{
assert(size() > 0); //断言,确保是否有数据
return *(_finish - 1);
}
vector<int> v4;
v4.push_back(1);
v4.push_back(2);
v4.push_back(3);
cout << v4.front() << endl;
cout << v4.back() << endl;
operator[ ]
????T& operator[](size_t n) ;
- 功能:访问下标为n处的值,返回值既可读又可写(非const对象)。
T& operator[](size_t n) //既可读又可写
{
return _start[n];
}
????const T& operator[](size_t n)const ;
- 功能:访问下标为n处的值,返回值只可读不可写(const对象)。
const T& operator[](size_t n)const //只可读不可写
{
return _start[n];
}
vector<int> v2(5, 2);
v2[2] = 3;
cout << v2[2] << endl;
const vector<int> v3(5, 4);
cout << v3[3] << endl;
数据修改操作
push_back
????void push_back(const T& val) ;
- 功能:在末尾插入一个元素。
void push_back(const T& val) //在末尾插入一个数据
{
if (_finish == _endofstorage) //空间满了,扩容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = val; //插入数据
_finish++;
}
pop_back
????void pop_back( ) ;
- 功能:删除最后一个元素。
void pop_back() //删除最后一个元素
{
assert(size() > 0); //断言,无任何数据,不能在进行删除操作
_finish--;
}
vector<int> v4;
v4.push_back(1);
v4.push_back(2);
v4.push_back(3);
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
v4.pop_back();
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
swap
????void swap(vector& v) ;
- 功能:交换。
void swap(vector<T>& v) //交换
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector<int> v2(5, 2);
vector<int> v4;
v4.push_back(1);
v4.push_back(2);
v4.push_back(3);
v4.pop_back();
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
v2.swap(v4);
for (auto& e : v2)
{
cout << e << ' ';
}
cout << endl;
for (auto& e : v4)
{
cout << e << ' ';
}
cout << endl;
clear
????void clear( ) ;
- 功能:使vector中元素的总个数size变为0,但容量capacity不变。
void clear() //清空 size改变,capacity不变
{
_finish = _start;
}
insert
????void insert ( iterator position , const typename& x) ;
- 功能:在指定的位置(迭代器)前插入元素x。
iterator insert(iterator pos, const T& val) //在pos位置前插入元素
{
assert(pos >= _start && pos <= _finish); //断言,确保在[_start,_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,又可以用迭代器
//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove为值拷贝
iterator tmp = _finish - 1;
while (tmp >= pos)
{
*(tmp + 1) = *tmp;
tmp--;
}
*pos = val; //插入数据
_finish++;
return pos; //返回值为了,发生扩容,pos位置更新后的值仍能被继续使用
}
pos位置未更新
void insert(iterator pos, const T& val) //在pos位置前插入元素
{
assert(pos >= _start && pos <= _finish); //断言,确保在[_start,_finish]范围内插入数据
if (_finish == _endofstorage) //空间满了,扩容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
//此处数据往后挪动,既可以用memmove,又可以用迭代器
//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove为值拷贝
iterator tmp = _finish - 1;
while (tmp >= pos)
{
*(tmp + 1) = *tmp;
tmp--;
}
*pos = val; //插入数据
_finish++;
}
vector<string> v1;
v1.push_back("zhangsan");
v1.push_back("lisi");
v1.
上一篇:
Python中的Lambda函数
推荐阅读
-
10.列表的模拟实现(普通迭代器和常量迭代器的类模板)
-
对话NGC蔡岩:从机制创新到价值沉淀,解析DeFi产品开发逻辑 |链捕手 - 真正的DeFi产品首先要有足够的安全性和稳定性,如果能在此基础上有一些功能创新,那就非常好了。像 Uniswap 这样逐渐成为 DeFi 基础架构的产品,可遇而不可求。 链式捕手:固定利率协议之前关注度比较高,但观察下来发现,大部分协议还是类似于传统金融CDO(抵押债务凭证)的玩法,风险系数很高,您如何理解这块业务的价值和风险? 蔡岩:确实有些定息协议类似CDO玩法,背后绑定一个债券,但并不是所有的定息协议都是这样的玩法,像这种CDO玩法的主要代表项目是88mph,背后绑定的是Aave、Compoud这样的借贷协议,在此基础上做定息和浮息债券;像APWine,背后同样是Aave,它会发行期货收益代币来锁定你的收益;Notional本身是做借贷市场的,在此基础上做定息协议。 非 CDO 的玩法,比如 Horizon,更像是一个利率撮合器,背后需要用户通过拍卖产生更合适的目标收益率;像 Saffron、BarnBridge 等是通过风险分级来定义不同的收益率。总的来说,创新还是挺多的。 价值层面是创新和想象力,因为在传统金融领域,比如银行做固定收益证券,或者评级机构给风险分级,这些业务都非常大,利润也很丰厚。而 DeFi 的对口业务给了类似业务很大的想象空间。尤其是固定利率协议的成熟产品不多,尝试各种微创新是很有意义的。 风险程度还是要具体到不同的玩法,比如,在 Aave、Compoud 等借贷协议的固定利率协议背后,如果这些借贷协议受到攻击,与之绑定的固定利率协议也会受损。 同样,如果自己做借贷市场,可能更需要更强的开发能力。再有,如果该程序的机制或参数设计不当,同样会导致协议运行不稳定,并可能造成大量用户清盘。 总的来说,风险在于固定利率协议的设计,这是一个非常复杂的过程,需要不断地尝试和出错。 链式捕捉器:刚刚提到背后是Aave/Compound的固定费率协议风险较大,您认为Aave最大的不确定性和创新点分在哪里? 蔡岩:其实爱钱进一直被认为是走在行业前列的项目,他们的迭代速度非常快,比如率先尝试闪贷、推出新的经济激励模式、推出目前业内首个安全模块、尝试L2解决方案等等。 而在主要的借贷业务上,他们又十分谨慎,比如在抵押率、清算系数等风险参数的设计上相对于其他借贷协议较为保守,并不会存在为了吸引更多借贷资金而降低风险的要求。 与许多 DeFi 项目一样,即使 Aave 进行了多次审计,也无法保证不存在漏洞。前段时间,Aave 刚进入 V2 阶段时,白帽黑客就指出了某个漏洞。 之前的创新点可能是闪电借贷,这是当时业内独一无二的新产品功能,也为 Aave 带来了不少收益。当然,也有人批评闪电贷只能方便黑客实现资金效益的最大化,但工具本身并没有错,未来闪电贷肯定会有更多的应用场景。 其次是安全模块的设计,这有点像项目本身的储备金库,保障项目的安全性,这也是爱维开创的先河。说实话,目前大多数项目都没有做到代币模式的良性或正向运营,也做不到像Aave一样的安全模块,这是一个不小的门槛。 Chaincatcher从某种程度上来说,挖矿模式是DeFi财富效应的根本支撑,但Aave的CEO却说挖矿机制带来的动力是不可持续的,您怎么看这个观点? 蔡岩:"挖矿机制 "不可能失效,因为它是一种激励机制,或者说是项目冷启动的一种方式。但流动性开采亚博体育手机客户端不会一直高涨。比如去年11月的流行性挖矿高APY持续了一两个月就崩盘了,导致DeFi市场大幅回调。 Aave、Uniswap、Synthetix等项目真正爆发进入市值前15名也是在今年2月,我更倾向于这是头部DeFi长期价值的体现。虽然大家都喜欢抢高APY的矿机,但我个人很少参与挖矿,所以我并不觉得流动性挖矿是DeFi的基本面支撑。
-
【C++】vector模拟实现+迭代器失效