当前位置：网站首页>vector的模拟实现
vector的模拟实现
2022-06-21 16:08:00 【Hero 2021】
文章目录
一、vector中常用类成员
namespace sjj//自定义命名空间与标准库中的以区别开来
{
template<class T>//类模板
class vector
{
public:
typedef T* iterator; //类型指针
typedef const T* const_iterator;
vector(); //构造函数1
template<class InputIterator>;//用一段迭代器区间去初始化，为了支持任意类型，用到了模板
vector(InputIterator first, InputIterator last);//构造函数2
vector(const vector<T>& v); //拷贝构造函数
vector<T>& operator=(vector v); //赋值运算符重载
~vector(); //析构函数
//迭代器相关的函数
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end()const;
//容量大小相关的函数
size_t size()const;
size_t capacity()const;
bool empty();
//扩容相关的函数
void reserve(size_t n);
void resize(size_t n, const T& val = T());
//插入数据相关的函数
iterator insert(iterator pos, const T& x);//在pos位置之前插入数据x
void push_back(const T& x); //尾插
//删除数据相关的函数
void pop_back();
iterator erase(iterator pos);
//下标访问相关的函数
T& operator[](size_t i);
const T& operator[](size_t i)const;
//其他函数
void Swap(vector<T>& v);
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
二、vector的底层结构
我们就用这三个私有成员来模拟实现我们的vector
iterator _start;//开始位置的指针
iterator _finish;//结束的下一个位置的指针
iterator _endofstorage;//最大容量的下一个位置的指针
三、vector的默认成员函数
构造函数1—空构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
}
构造函数2—迭代器区间构造
//用一段迭代器区间去初始化，为了支持任意类型，用到了模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
拷贝构造函数
写法一：传统写法
//传统写法
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
//void * memcpy ( void * destination, const void * source, size_t num );
memcpy(_start,v._start,sizeof(T)*v.size());
}
写法二：现代写法（更推荐）
//现代写法
vector(const vector<T>& v)//v是一个局部对象，出了作用域自动调用析构函数，不用管它
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());//利用迭代器区间进行初始化tmp
Swap(tmp);//交换this对象和tmp对象里面的值
}
赋值运算符重载
写法一：传统写法
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v) //防止自己给自己赋值
{
delete[] _start; //释放原来的空间
_start = new T[v.capacity()]; //新开辟一块和容器v大小相同的空间
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //更新_finish
_endofstorage = _start + v.capacity(); //更新_endofstorage
}
return *this; //支持连续赋值，返回引用
}
写法二：现代写法(更加推荐)
vector<T>& operator=(vector v)
{
Swap(v);
return *this;//为了支持连续赋值，返回引用
}
析构函数
//析构
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
//全部置空
四、迭代器相关的函数
迭代器的分类
每一种迭代器都有着命名的规范，我们可以通过英文见名知意。
每一个迭代器越往上，权限就越小，我们可以把下面的迭代器看做父类，越往上的迭代器就是子类，它们有着父类的相关操作，但是我们传入迭代器时，只能传入权限大于等于当前迭代器的类型,例如我们reverse函数，需要传入双向迭代器，它可以传双向、随机，但是不能传权限比他小的迭代器，否则就会报错
通过查看文档我们可以看到一些函数需要传入迭代器类型：
迭代器对应的STL容器分类
举个例子：
int main()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(4);
v1.push_back(3);
v1.push_back(6);
sort(v1.begin(), v1.end());//正确使用
list<int> lt;
lt.push_back(1);
lt.push_back(3);
lt.push_back(2);
lt.push_back(4);
sort(lt.begin(),lt.end());//这里会报错
return 0;
}
list使用的是双向迭代器，sort要求传入随机迭代器，权限被缩小了，这是错误的使用
迭代器失效问题
问题引出：
void insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);//暴力检查
if (_finish == _endofstorage)//检查是否需要扩容
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
//插入x
iterator end = _finish - 1;
while (end>=pos)
{
*(end +1) = *end;//前一个挪到后一个位置
--end;
}
*pos = x;
++_finish;
}
//测试
void test()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = find(v.begin(), v.end(), 2);//找到值为2的位置
if (it != v.end())
{
// 如果insert中发生了扩容，那么会导致it指向空间被释放
// it本质就是一个野指针，这种问题，我们就叫迭代器失效
v.insert(it, 20);
}
for (auto e : v)
{
cout << e << " ";
}
}
怎么造成迭代器失效的呢？
原因：插入数据扩容的时候，我们定义了一个pos位置和end位置两个迭代器，新空间中，没有pos位置，但是原来的就空间还有个pos迭代器，任然指向一个已经被返还给操作系统的空间，但是最后居然*pos，解引用插入数据了，这显然是个野指针问题，存在着内存泄漏的风险。
改正解决迭代器失效的办法：在使用前，对迭代器重新进行赋值即可，我们需要更新一下扩容后的新的pos位置，并且我们在外部传参时，形参的改变不会影响实参，所以我们要传insert的pos位置的返回值，我们才能真正的删除pos位置的数据
//在pos位置之前插入数据x
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);//暴力检查
assert(pos <= _finish);
if (_finish == _endofstorage)//检查是否需要扩容
{
//扩容会导致pos位置迭代器失效，所以需要更新一下新位置的pos
size_t len = pos - _start;//记录一下pos距离_start位置的长度
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新一下扩容后的pos
}
//插入x
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;//返回新空间pos位置，因为形参的改变不会影响实参
}
同样erase中也存在着迭代器失效的问题
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;//pos的下一个位置记作begin
while (begin < _finish)
{
*(begin - 1) = *begin;//数据从后往前覆盖
++begin;
}
--_finish;//数据个数减一，finish也减一
}
void test()
{
// 三种场景去测试
// 1 2 3 4 5 -> 正常
// 1 2 3 4 -> 崩溃
// 1 2 4 5 -> 没删除完
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(4);
v1.push_back(5);
//v1.push_back(5);
// 要求删除v1所有的偶数
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
v1.erase(it);
}
++it;
}
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
这里最大的问题就是，erase(it)后，it的意义已经变了，就是迭代器失效了，直接++it可能不导致一些意料之外的结果，如果是连续的偶数，会直接跳过后一个偶数，导致后一个偶数没有被删除掉。
正确的erase函数：
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;//pos的下一个位置记作begin
while (begin < _finish)
{
*(begin - 1) = *begin;//数据从后往前覆盖
++begin;
}
--_finish;//数据个数减一，finish也减一
return pos;//传pos位置的迭代器，防止迭代器失效
}
void test()
{
// 三种场景去测试
// 1 2 3 4 5 -> 正常
// 1 2 3 4 -> 崩溃
// 1 2 4 5 -> 没删除完
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(4);
v1.push_back(5);
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
it = v1.erase(it);//传it位置的返回值，更新pos位置，这样就不会导致迭代器失效的问题了
}
else
{
++it;
}
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
迭代器相关的函数
其实vector中的迭代器就是原生类型的指针，只不过是经过typedef的
typedef T* iterator;
typedef const T* const_iterator;
begin()和end()函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const版本的begin()和end()函数
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
五、vector中容量大小相关的函数
我们这里就可以利用C语言学到的，两个指针的差值就是两个指针指向间的元素个数
size()函数
size_t size()const
{
return _finish - _start; //返回容器当中有效数据的个数
}
capacity()函数
size_t capacity()const
{
return _endofstorage - _start; //返回当前容器的最大容量
}
empty()函数
bool empty()const
{
return _start == _finish;
}
六、vector中扩容相关的函数
reserve()函数
void reserve(size_t n)
{
if (n > capacity())
{
//扩容
size_t sz = size();
T* tmp = new T[n];//新开一段空间
if (_start)
{
//void* memcpy(void* dest, const void* src, size_t count);
memcpy(tmp, _start, sizeof(T) * size());//memcpy是浅拷贝，数据是内置类型不影响，是自定义类型会崩溃
delete[] _start;//释放掉原来的空间
}
_start = tmp;//交换指针指向
//扩完容以后_finsih _endodstorage也要处理一下
//要把原来的size保存一下
//_finish = _start + size();//size=finish-start start已经被更新了
_finish = _start + sz;
_endofstorage = _start + n;
}
}
使用memcpy拷贝问题
我们这里如果vector中存入的是string等自定义类型，使用memcpy进行拷贝，会出现什么问题呢？
int main()
{
sjj::vector <string> v;
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
return 0;
}
问题分析：
- memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
- 如果拷贝的是内置类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
- 插入的字符串长一些的话，就会出现乱码
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
我们作出的改变就是不用memcpy，我们手动将数据一个一个的拷贝过去。我们能够间接调用string的赋值运算符重载，实现string的深拷贝。
出现乱码：VS下作了一个优化，当数据字长较小时(小于16时)，它会把数据存入一个char _Buf[16]的数组中，当数据长一点，它会把数据存入一个堆上开辟的大数组中char * _ptr中。
//代码修正
//memcpy(tmp, _start, sizeof(T) * size());//memcpy是浅拷贝
for (size_t i = 0; i < sz; ++i)
{
//当T是int等内置类型，一个一个拷贝没有问题
//当T是string等内置类型，会去调用它的深拷贝
tmp[i] = _start[i];
}
resize()函数
我们这里需要考虑两种情况
第一种：
第二种：
void resize(size_t n, const T& val = T())// 给T()缺省值，int()
{
//分两种情况
//第一种n<size
//第二种n>capacity需要扩容
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
七、vector的增加数据相关的函数
push_back( )
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
//复用reserve函数
reserve(capacity() == 0 ? 4 : capacity() * 2);
//如果当前的capacity是0，扩到4，如果不是0，就扩2倍
}
*_finish = x;
++_finish;
}
insert()函数
//在pos位置之前插入数据x
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);//暴力检查
assert(pos <= _finish);
if (_finish == _endofstorage)//检查是否需要扩容
{
//扩容会导致pos位置迭代器失效，所以需要更新一下新位置的pos
size_t len = pos - _start;//记录一下pos距离_start位置的长度
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新一下扩容后的pos
}
//插入x
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;//返回新空间pos位置，因为形参的改变不会影响实参
}
八、vector的删除数据相关的函数
pop_back()函数
void pop_back()
{
assert(_finish > _start);//暴力检查一下，防止越界
--_finish;//将_finish减减，相当于就把尾上的数据删除了
}
erase()函数
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;//pos的下一个位置记作begin
while (begin < _finish)
{
*(begin - 1) = *begin;//数据从后往前覆盖
++begin;
}
--_finish;//数据个数减一，finish也减一
return pos;//传pos位置的迭代器，防止迭代器失效
}
九、vector的查找数据相关的函数
operator[ ]下标查找
//普通版本
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
//const版本
const T& operator[](size_t i)const
{
assert(i < size());
return _start[i];
}
十、其他函数
swap()函数
void Swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
边栏推荐
- 函数调用模型
- PTA l3-031 thousand hand Guanyin (30 points)
- Accélérer le déploiement de l'application Native Cloud et compléter l'authentification de compatibilité entre Yanrong yrcloudfile et Tianyi Cloud
- module. Exports points to problems
- [issue 349] Interviewer: how to gracefully customize the ThreadPoolExecutor thread pool?
- path. join() 、path. Basename() and path extname()
- 窗帘做EN 1101易燃性测试过程是怎么样的？
- Nanjing University static program analyses -- Introduction learning notes
- node服务器 res.end()中写中文，客户端中乱码问题的解决方法
- 【mysql学习笔记14】DQL语句执行顺序
猜你喜欢
![[MySQL learning notes 17] sorting out common functions](/img/11/cb4ea6750cc6dca5a39a65de443074.png)
[MySQL learning notes 17] sorting out common functions
MySQL 1055错误-this is incompatible with sql_mode=only_full_group_by解决方案
函数调用模型
Google play 应用签名密钥证书，上传签名证书区别
![[MySQL learning notes 15] user management](/img/e8/4773f99c42891789b0311506b8384f.png)
[MySQL learning notes 15] user management
![[MySQL learning notes 18] constraints](/img/29/c72f83bfae8fd8b43e78cdf1aa9cbc.png)
[MySQL learning notes 18] constraints
![[graduation n-year series] the fourth year of graduation](/img/0a/e7d903dec475c54ba1277fe133963f.png)
[graduation n-year series] the fourth year of graduation
Jetpack Compose 的阶段
大话内存四区
Integrated base scheme presentation
随机推荐
Bm95 points candy problem
AttributeError: ‘Book‘ object has no attribute ‘sheet‘
＃Vscode工具＃
AS 3744.1标准中提及ISO8191测试，两者测试一样吗？
一招教你通过焱融 SaaS 数据服务平台+ELK 让日志帮你做决策
【没搞懂路由策略？盘它！】
go corn定时任务简单应用
Simple ideas and procedures for quick sorting
变量
[MySQL learning notes 12] paging query
[MySQL learning notes 17] sorting out common functions
module. Exports points to problems
加速云原生应用落地，焱融 YRCloudFile 与天翼云完成兼容性认证
Kotlin annotation declaration and use
JetPack compose 状态提升（二）
LeetCode_字符串_简单_387. 字符串中的第一个唯一字符
SCAU软件工程基础
regular expression
Function call model
3M mutual aid intelligent contract system development and construction technology