自学内容网 自学内容网
自学内容网 > 正文

【C++初阶】vector模拟实现

🕗 发布于 2024-09-19 21:58 c++  android  开发语言  入门  编程语言  

请添加图片描述

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍋vector模拟实现

🍑默认成员函数

🍍构造函数

//默认构造
vector()
{}

//带参构造
vector(size_t x, const T& val = T())
{
resize(x, val);
}

......

对于带参构造当中，第二个参数，所采用的是匿名对象作为缺省值；因为在这里T的的类型不确定，只能使用匿名对象来修饰。

匿名对象：指的是没有被显式命名（即没有标识符或变量名）的对象实例。这类对象通常在需要临时执行某些操作或作为函数参数/返回值传递时创建，而不需要将结果长期存储于某个变量中。

此处的构造只涉及到浅拷贝，对于深拷贝后面会有介绍。

🍍拷贝构造函数

//拷贝构造(普通写法)
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}



//拷贝构造(实用写法)
vector(const vector<T>& v)
{
reserve(v.capacity());
for (const auto& in : v)
{
push_back(in);
}
}

//现代写法
vector(vector<T>& v)
{
vector<T> ret(v.begin(), v.end());
swap(ret);
}

此处的拷贝构造函数就涉及到深拷贝问题，这里我提供了三种写法。
(1)第一种写法就是普通的写法，相信大家自己来模拟拷贝构造，思路大径相同；这里还用到了memmove()函数， 大家也可以采用while()循环的方式来代替，方法多种多样。
(2)第二种写法就是利用vector的插入完成，不过需要提前开满足够的空间，不然内存会泄露。
(3)第三种写法利用swap的特性。

🍍析构函数

//iterator _start = nullptr;
//iterator _finish = nullptr;
//iterator _endofstorage = nullptr;

~vector()
{
if(_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endofstorage = nullptr;
}
}

析构函数还是常规写法，没有什么特别之处。
_start、_finish、_endofstorage是vector的迭代器。_start是指向头；_finish是数据存储大小的尾;_endofstorage是整个空间大小的尾。

🍍赋值重载函数

//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
reserve(v.capacity());
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
_finish = _start + v.size();
}
return *this;
}

//优化写法
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}

在进行赋值重载操作时，可以先对数据进行对比，如果相同就不用再进行此操作。
赋值重载需要注意的是优化写法中在参数中没有采用引用的写法，swap()函数是把两处的内容完全交换，而我们在这里仅仅只需要赋值，所以我在这里并对v采用引用的写法，如果对v采用引用的写法可能会把原有的v中数据破坏，未被引用的v仅仅只是原来v中数据的拷贝，虽然它俩名字相同，但作用域不同。

🍑迭代器

无论是范围for还是方括号进行遍历，底层原理都是迭代器,迭代器有两种版本，有const版本和非const版本；迭代器写法还是直接调用子函数进行实现。

iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}

🍑增删查改功能实现

🍍增加数据

  1. reserve()函数是扩容函数，capacity()函数是算出实际空间的大小，还额外使用了memcpy()函数进行了拷贝，这里之所以扩容在if条件下进行，是因为我们不仅仅是在插入数据的时候才用到扩容函数，比如赋值等等。
    这里还有一点需要注意，需要在_start空间释放前把实际数据的长度先保存，在这实际长度的计算是采用_finish-_start的长度，当我们已经释放_start，再次使用size()函数时，_start和_finish不在同一个物理量上，程序会报错，如下图：

在这里插入图片描述

void reserve(size_t n)
{
if (n > capacity())
{
size_t len = size();
T* tem = new T[n];
if (_start)
{
memcpy(tem, _start, len * sizeof(T));
delete[] _start;
}

_start = tem;
_finish = _start + len;
_endofstorage = _start + n;
}
}
  1. push_back()是尾插函数的实现，开头还是得先判断空间是否溢出再进行判断；_finish是实际数据大小的尾，_endofstorage是空间实际的大小，当这两者相等，空间就会溢出。reserve()函数是扩容函数。
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}

*_finish = x;
_finish++;
}
  1. Insert()函数是插入函数，在pos位置插入新的数据，还使用了memmove()函数进行了数据的移动，当然也可以使用while()和for()这两个也可以，看大家对那个熟悉就用那个。
    首先还是要先对pos位置进行判断，防止提供的pos位置有误；再用_finish与_endofstorage进行对比来判断空间是否溢出,是否需要扩容；最后再把pos位置往后的整体数据往后移一步，把新的数据插入pos位置即可。
void Insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}

memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
*pos = x;
++_finish;
}

🍍删除数据

  1. erase()函数是删除数据的函数。首先还是对题目提供的pos进行判断，我在这里就没有采用memmove()函数进行数据的移动，还是因为memmove()函数在删除末尾数据时有点问题，最后我还是采用while()循环来实现数据的移动。
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);

iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;

}
  1. pop_back()函数是尾删数据的函数，实现方式也是直接把_finish减一个数就可以，主要还是_finish是指向该数据的尾.
void pop_back()
{
assert(size() > 0);
--_finish;
}

🍍查找数据

  1. Find()函数是查找数据。实现方式也是利用迭代器进行遍历查找。
bool Find(T x)
{
iterator pos = _start;

while (pos <= _finish)
{
if (*pos == x) return true;
++pos;
}
return false;
}

🍍改变数据

  1. resize()函数是利用空间的性质对数据进行扩容和删除，也就是它既具有扩容的功能，又有删除的功能，还有增加数据的功能，只不过增加的是默认值0。

    参数中的T由于不确定类型所以采用的是匿名对象的缺省参数。该函数大家可以很少用到，下面是程序运行图：

在这里插入图片描述

void resize(size_t n, T val = T())//匿名对象的缺省值
{
if (n > size())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}

🍍其它程序

  1. size()函数是计算实际数据大小，capacity()函数是计算实际空间的大小，当实际数据大小等于实际空间的大小，该空间就满了，再往里插入新数据，空间就会溢出。
size_t size() const
{
return _finish - _start;
}

size_t capacity() const
{
return _endofstorage - _start;
}
  1. operator函数是方便该类数据可以使用方括号进行遍历，也就是数组的方式进行遍历。也是有两个版本，一个是const类，另一个是非const类。
T& operator[](const T& pos)
{
assert(pos < size());
return _start[pos];
}

const T& operator[](const T& pos) const
{
assert(pos < size());
return _start[pos];
}

🍑vector模拟整体代码

#include<iostream>
#include<assert.h>

using namespace std;



namespace ciking
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

vector()
{}


//拷贝构造(普通写法)
/*vector(const vector<T>& v)
{
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}*/

//拷贝构造(实用写法)
vector(const vector<T>& v)
{
reserve(v.capacity());
for (const auto& in : v)
{
push_back(in);
}
}

void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}

vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}

~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}

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())
{
size_t len = size();
T* tem = new T[n];
if (_start)
{
memcpy(tem, _start, len * sizeof(T));
delete[] _start;
}

_start = tem;
_finish = _start + len;
_endofstorage = _start + n;
}
}

void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}

*_finish = x;
_finish++;
}

void pop_back()
{
assert(size() > 0);
--_finish;
}

void Insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}

memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
*pos = x;
++_finish;
}

void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
//memmove(pos, pos + 1, sizeof(T) * (_finish - pos));
//--_finish;

iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;

}

bool Find(T x)
{
iterator pos = _start;

while (pos <= _finish)
{
if (*pos == x) return true;
++pos;
}
return false;
}

void resize(size_t n, T val = T())//匿名对象的缺省值
{
if (n > size())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}

size_t size() const
{
return _finish - _start;
}

size_t capacity() const
{
return _endofstorage - _start;
}

T& operator[](const T& pos)
{
assert(pos < size());
return _start[pos];
}

const T& operator[](const T& pos) const
{
assert(pos < size());
return _start[pos];
}

private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};

void print_vector(const vector<int>& v)
{
for (auto in : v)
{
cout << in << " ";
}
cout << endl;
}

void test_vector1()
{
vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);
vv.push_back(4);
vv.push_back(4);
vv.push_back(4);
vv.push_back(4);
vv.push_back(4);

vector<int>::iterator it = vv.begin();
while (it != vv.end())
{
cout << *it << " ";
it++;
}
cout << endl;

vv.erase(vv.end());

for (auto in : vv)
{
cout << in << " ";
}
cout << endl;

for (size_t i = 0; i < vv.size(); i++)
{
cout << vv[i] << " ";
}
cout << endl;

vv.Insert(vv.begin(), 100);
print_vector(vv);

vector<int> v2;
v2.push_back(100);
v2.push_back(120);
v2.push_back(130);
v2.push_back(140);

vv = v2;

for (size_t i = 0; i < vv.size(); i++)
{
cout << vv[i] << " ";
}
cout << endl;
}

void test_vector2()
{
vector<int> v1;
v1.push_back(100);
v1.push_back(110);
v1.push_back(120);
v1.push_back(130);
v1.push_back(140);
v1.push_back(150);
v1.push_back(160);
v1.push_back(170);
v1.push_back(180);
v1.push_back(190);
v1.push_back(200);

cout << "原有数据:";
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;

v1.resize(15);

cout << "resize(15)空间变大后的数据:";
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;


v1.resize(8);

cout << "resize(8),空间变小的数据:";
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;




}


}


int main()
{
ciking::test_vector2();

return 0;
}

关于本章知识点如果有不足或者遗漏，欢迎大家指正，谢谢！！！

请添加图片描述

请添加图片描述


原文地址：https://blog.csdn.net/weixin_74967884/article/details/142330386

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

  • 算法笔试-编程练习-好题-07

    如果不熟悉python的底层的话，上面的程序看起来就是O(n)的时间复杂度。但是由于python的字符串类型的变量底层上是不可变的，因此每一次的+=，都需要经历：1）计算两边的字符串的长度，2）然后开

    阅读更多2024-09-22
  • 如何导出数据库时将ID也导出

    如果你使用的是某种框架或工具（如 Sequelize、Django ORM 等），可以考虑使用这些工具提供的迁移或数据导出功能。你可以使用 SQL 脚本导出数据库，包括表结构和数据。这种方式可以确保数

    阅读更多2024-09-22
  • Java stream流根据对象属性去重

    以下是一个示例，展示了如何根据对象的某个属性去重，并保留具有该属性值的第一个或最后一个遇到的对象。.values().stream().collect(Collectors.toList())：从Ma

    阅读更多2024-09-22
  • js进阶——函数作用域和块作用域

    理解这些作用域概念和使用场景，能帮助开发者更好地控制代码的可维护性与性能，特别是在处理复杂逻辑时，掌握作用域的原理能避免许多常见的 JavaScript 错误。IIFE 的核心特点是，它能够创建一个独

    阅读更多2024-09-22
  • 使用Properties

    iii.读写Properties时，使用getProperty()和setProperty()方法，不要调用继承自HashTabled的get()和put()方法（历史遗留问题）。i.它的Key-Va

    阅读更多2024-09-22
  • 招商银行招行笔试难度递增？要点解读

    星R] 行测55min 言语理解+数学计算+思维策略55题，每道题做完后不允许返回修改，这部分建议求稳为主，你永远不知道下一 [星R] 游戏化测评包括找不同、记忆题和小球追踪，整天难度也较大，但和性

    阅读更多2024-09-22
  • pytorch 同步机制

    在 PyTorch 中，当多个算子（operators）和内核（kernels）被并行执行时，PyTorch 通过 CUDA 的和机制来管理并发和同步。CUDA 是一个异步计算平台，计算任务会被放入一

    阅读更多2024-09-22
  • springboot集成rabbitmq

    注意：客户端和服务器端不能在同一个服务，必须分开两个服务写。只需要监听deadLetterQueue队列的消息。用于监听客户端发送过来的消息。

    阅读更多2024-09-22
  • IO流（java）

    IO流概述IO流的分类IO流总体来看就有四大流IO流的体系FilelnputStream（文件字节输入流）作用：以内存为基准，可以把磁盘文件中的数据以字节的形式读入到内存中去。构造器说明创建字节输入流

    阅读更多2024-09-22
  • WSL迁移Linux系统到非系统盘（完整实操版）

    本文提供了使用 WSL 将 Linux 系统迁移到非系统盘的详细指南。步骤包括确认系统存在、导出系统为 tar 包、删除原系统、在目标盘创建存放文件夹、导入 tar 包回 Linux 系统、验证迁移成

    阅读更多2024-09-22
自学内容网
Copyright © 2015-2024