当前位置：网站首页>vector的使用和模拟实现:
vector的使用和模拟实现:
2022-08-02 03:32:00 【RNGWGzZs】
--------------血雨腥风，是对行远人的痛快的激励
目录
(1)Vector是什么？
vector是表示可变大小数组的序列容器。和数据结构的 顺序表尤为相似。
因为模板的介入，vector能存储的类型多样，且方便。
(2)Vector的功能使用:
同上篇string(串)的功能 差不多，vector的基本功能颇为丰富:
①构造类:
(constructor)构造函数声明 | 函数说明 |
vector() | 无参构造 |
vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
vector (const vector& x); | 拷贝构造 |
vector (InputIterator fifirst, InputIterator last); | 使用迭代器进行初始化构造 |
② 容量空间:
容量空间 | 函数说明 |
| size | 有多少个有效数据 |
| capacity | vector的总容量 |
| empty | 有没有数据 |
| resize | 扩容，并初始化 |
| reserve | 扩容 |
resize:
reserve:
③modify:
vector增删查改 | 函数说明 |
| push_back | 尾插 |
pop_back | 尾删 |
find | 查找 |
insert | 在position之前插入val |
erase | 删除position位置的数据 |
swap | 交换两个vector的数据空间 |
operator[] | 像数组一样访问 |
push_back\pop_back:
find\ insert;erase:
注:erase 和 insert的 参数是迭代器>
insert:
erase:
(2)Vector的模拟实现:
namespace dy
{
//vector 是可以存储多种类型的顺序表
template<class T>
class vector
{
//vector的迭代器是个原生指针
typedef T* iterator;
typedef const T* const_iterator;
public:
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}①构造:
//无参构造
vector()
: _start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{}
//迭代器构造
template<class templateiterator>
vector(templateiterator first, templateiterator last)
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{
while (first != last)
{
//复用尾插
push_back(*first); //push_back 之后会实现
first++;
}
}
//默认值初始化
vector(size_t n, const T& val = T()) //因为缺省值不知道 具体给什么，所以就用匿名对象
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{
reserve(n); //开辟n个空间
while (n--)
{
push_back(val);
}
}
//析构
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}capactiy、size、operator[] :
size_t capacity() const
{
return _endofstorage-_start; //起始位置减去 容量位置
}
size_t size() const //最好+上
{
return _finish-_start; //起始位置减去 最后数字的位置
}
T& operator[](size_t pos)
{
assert(_start+pos < _finish)
return _start[pos];
}拷贝构造:
传统写法:
//传统写法
//拷贝构造
//s2(s1)
vector(const T& v)
:_start(new T[v.capacity()]), //开出同样大的空间
_finish(nullptr),
_endofstorage(nullptr)
{
//将s1 的数据拷贝给s2
memcpy(_start, v._start, sizeof(T) * v.size());
//更改_finish _endofstorage
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
//赋值运算符
//s1=s2
vector<T>& operator=(const vector<T>& v) //operator(&s1,s2);
{
if (this != &v) //自己和自己不赋值
{
delete[] _start; //先释放自己的空间
_start= new T[v.capacity()];
//拷贝数值
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
return *this;
}上面是传统写法，代码较为冗杂,
现代写法：
//现代写法:
void swap(const vector<T>& tmp)
{
//局部和全局分离
::swap(_start, tmp._start);
::swap(_finish,tmp._finish);
::swap(_endofstorage, tmp._endofstorage);
}
//赋值
vector<T>& operator=(const vector<T>& v)
{
if (*this != &v)
{
/*
swap(_start, tmp._start);
swap(_finish,tmp._finish);
swap(_endofstorage, tmp._endofstorage);
*/
//this->swap(tmp)
swap(tmp) //当然这三个swap实现的功能 一样 可以抽象出来
}
return *this;
}现代写法不仅兼顾了理解，且代码量少。
②modify:
push_back\reserve:
尾插框架很简单，就分是否需要扩容:
reserve的一大容易被忽略的点在这里。我们先看看测试:
//迭代器
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)
{
if (n > capacity()) //解耦
{
//新开 n 个空间
T* tmp = new T[n];
//避免找不到真正的size
size_t sz = size();
//可能_start为空
if (_start)
{
memcpy(tmp, _start, sizeof(T) * sz);
delete[] _start;
}
//更新
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n; //开辟了n个空间
}
}
void push_back(const T& val)
{
//需要增容
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; //2倍扩容
reserve(newcapacity);
}
*_finish = val; //直接怼_finish 解引用找到最后一数的下一个位置
_finish++;
} 
resize/pop_back:
尾删较为简单也就多赘述
bool empty()
{
return _finish = _start;
}
void pop_back()
{
assert(empty())
--finish;
}
void resize(size_t n, const T& val=T()) //给定缺省值
{
//1.缩减
if (n < size())
{
_finish = _start + n;
}
else
{
//统一是n>size()
if (n > capacity()) //如果需要的空间大 那么再去申请空间
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
}
③补充:
insert\erase:
在pos之前的位置，插入(insert)数值:
我们可以借助，库里面find函数，查找pos位置：
void Insert(iterator pos, const T& val)
{
assert(pos < _finish);
//扩容
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; //2倍扩容
reserve(newcapacity);
}
//挪动pos之后的数据
//从后往前
iterator end = _finish - 1;
while (end != pos)
{
*(end + 1) = *end;
--end;
}
//pos位置处 放val
*pos = val;
_finish++;
}
从结果上来看，我们代码与我们预期相同。然而真的是这吗？
此时我们换种情景:程序直接崩溃,而原因又在哪里呢？！
迭代器失效:
1.迭代器野指针:
我们不难猜到，问题最有可能出现的，就是在增容的部分，而恰恰第四次插入，就是需要增容~
所以，我们就需要对pos ，在扩容的时候，进行修正。
我们让gap记录 start 与 pos之间的相对差距。
void Insert(iterator pos, const T& val)
{
assert(pos < _finish);
//扩容
if (_finish == _endofstorage)
{
size_t gap = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; //2倍扩容
reserve(newcapacity);
pos = _start + gap;
}
//挪动pos之后的数据
//从后往前
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
//pos位置处 放val
*pos = val;
_finish++;
}2.迭代器代表的位置发生改变:
插入数据不可避免，会改变原先pos位置所指向的值。所以在用这种迭代器时，需要加点心。
erase:
我们根据库里的来模拟，erase除了删除pos位置的数值，还要返回pos位置，下一个的地址。
iterator erase(iterator pos)
{
//pos后的数 往前移动
iterator begin = pos + 1;
while (begin <= _finish)
{
*(begin - 1) = *begin;
begin++;
}
_finish--;
return pos;
}另:删除顺序表中的偶数
可能多数，认为删除偶数这样的逻辑是行得通的，比较也有结果。
只要找到偶数，就删掉。
换种数据就不行了。
所以，每次it进行判断的时候，每删除一个，还需要进行判断。
while (it != v1.end())
{
if (*it % 2 == 0)
{
it=v1.erase(it); //利用erase的返回值
}
else
{
it++;
}
}(3)深层次深拷贝:
大部分vector 重要的函数接口已经完成。
但，这样的vector在存储自定义类，而非内置类型是，会出现问题。
例如:
此时我们插入四个值，还算正常。
但当插入第五个数的时候。
所以问题还是在于，扩容。
但为啥，当数据足够长的时候，会出现乱字呢？！
在linux下，string不管有多长，都会存在“buf”里面，
但是在vs下，做了别的处理，
当串字符足够小，就存在_buf里面 ，越长 则存在_ptr
所以，这里用memcpy显然不合适，如果仅仅处理内置类型是足够的。
所以和memcpy有关的，就需要更改:
//拷贝构造
//s2(s1)
vector(const vector<T>& v)
:_start(nullptr), //开出同样大的空间
_finish(nullptr),
_endofstorage(nullptr)
{
reserve(v.capacity()); //进行增容
for (auto e : v)
{
push_back(e);
}
//传统写法
//_start = new T[v.capacity()];
将s1 的数据拷贝给s2
memcpy(_start, v._start, sizeof(T) * v.size());
//int sz = size();
深层次考别
//for (size_t i = 0;i < v.size();i++)!!
//{
// _start[i] = v._start[i];
//}
更改_finish _endofstorage
//_finish = _start + v.size();
//_endofstorage = _start + v.capacity();
}
void reserve(size_t n)
{
if (n > capacity()) //解耦
{
//新开 n 个空间
T* tmp = new T[n];
//避免找不到真正的size
size_t sz = size();
//可能_start为空
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * sz);
for (size_t i = 0;i < sz;i++)
{
//复用 赋值运算符 这是深拷贝~
tmp[i] = _start[i];
}
delete[] _start;
}
//更新
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n; //开辟了n个空间
}
}
vector也就告一段落啦！
祝你好运~
边栏推荐
猜你喜欢
HDMI转MIPI CSI东芝转换芯片-TC358743XBG/TC358749XBG
C语言教程 - 制作单位转换器
工业边缘网关究竟强大在哪里？
TeamCode 产品 UI 全新升级，快来体验吧
出差电子流应用实战
Type c PD 电路设计
Host your own website with Vercel
【Popular Science Post】Detailed explanation of MDIO interface
MIPI解决方案 ICN6202：MIPI DSI转LVDS转换芯片
【Popular Science Post】UART Interface Communication Protocol
随机推荐
博达工业云与阿里云对比
实现动态库（DLL）之间内存统一管理
bluez5.50+pulseaudio实现蓝牙音响音频播放
LL（1）文法 ：解决 if-else/if-else 产生式二义性问题
【TCS3200 颜色传感器与 Arduino 实现颜色识别】
openmv学习 2022.5.9
树莓派4B打开文件管理时出现闪退
调试九法准则
【nRF24L01 connects with Arduino to realize wireless communication】
【plang 1.4.4】编写茶几玛丽脚本
【Popular Science Post】Detailed explanation of MDIO interface
阿里云华为云对比分析
【霍尔效应传感器模块与 Arduino】
【Popular Science Post】UART Interface Communication Protocol
MC1496乘法器
idea中创建jsp项目详细步骤
单火线开关设计详解
【plang1.4.3】编写水母动画脚本
Lightly 支持 Markdown 文件在线编写（文中提供详细 Markdown 语法）
GM7150，振芯科技，视频解码器，CVBS转BT656/601，QFN32，替换TVP5150/CJC5150