手写线性表C++ vector

目录

一、vector基本概念

1.1、构造函数

1.2、析构函数

1.3、插入元素

1.4、删除元素

1.5、重载运算符

二、完整代码


一、vector基本概念

C++中的vector是一种动态数组,它可以根据需要自动调整大小。vector是C++标准模板库(STL)中的一个容器,它可以存储任意类型的元素,如整数、浮点数、字符串等。使用vector时,不需要关心数组的大小,因为它会自动管理内存。

vector的基本操作包括添加元素、删除元素、访问元素等。例如,可以使用push_back()函数向vector末尾添加元素,使用pop_back()函数删除vector末尾的元素,使用下标访问元素等。此外,vector还支持迭代器,可以方便地遍历vector中的所有元素。

vector的优点包括:

  1. 动态调整大小,不需要预先分配固定大小的内存;
  2. 支持随机访问,访问速度较快;
  3. 提供了丰富的成员函数,方便操作。

然而,vector的缺点是插入和删除元素的效率较低,因为可能需要移动大量元素来重新排列。在需要频繁插入和删除元素的场景下,可以考虑使用其他容器,如list。C++ STL中已经有了vector,其底层数据结构就是线性表,你可以理解为:动态数组,他在内存中存储是连续的,而链表就不是线性的。本文使用c++自定义个MyVector类。

1.1、构造函数

MyVector类需要维护三个成员:

  •     int* array_:假定这是一个int型动态数组
  •     int size_:表示当前数组中已经塞进去几个元素
  •     int capacity_:表示当前数组最多能塞进几个元素,如果容量不够,还要扩容,后面会讲,注:size_ <= capacity_
MyVector::MyVector()
{
    size_ = 0;
    capacity_ = 10;
    array_ = new int[capacity_];
}

1.2、析构函数

没什么特别的地方,就是delete[]成员array_就行。

MyVector::~MyVector()
{
    delete[] array_;
    cout << "free " << array_ << endl;
}

1.3、插入元素

实现一个push_back方法,和std::vector一样的。插入元素的时候,要判断容量是否用完;如果空间不够,那就申请一块更大的空间,再将原来的数据拷贝过来,然后释放原来的数据,最后插入新的元素。所以,这里应该知道,std::vector是的使用的时候,最好能够预留好(reserve)合适的空间。

void MyVector::push_back(int value)
{
    if (empty()) return;
    //判断空间是否足够
    if (size_ == capacity_)
    {
        int* newspace = new int[capacity_ * 2]; // 扩容
        memcpy(newspace, array_, capacity_ * sizeof(int));// 备份 - > newsapce
        delete[] array_;// 删除旧空间
        capacity_ *= 2;//扩容
        array_ = newspace;//转移旧空间的值 - > 新空间
    }
    //在末尾插入元素
    array_[size_] = value;
    size_++;
}

1.4、删除元素

给定需要删除元素的索引pos或者value,就能删除元素。C++ STL中的std::vector删除元素和这里一样,都会涉及拷贝数据。

依据索引pos删除元素:

void MyVector::removeByPose(int pos)
{
    if (empty()) return;
    if (pos < 0 || pos >= size_)//越界
    {
        cout << "out of range!" << endl;
        return;
    }
    for (int i = pos; i < (size_ - 1); i++) //注意越界
    {
        array_[i] = array_[i + 1];
    }
    size_--;
}

依据索引值value删除元素:

void MyVector::removeByValue(int value)
{
    if (empty()) return;
    int pos = find(value);
    if (pos == -1)
    {
        cout << "没有元素:" << value << endl;
        return;
    }
    removeByPose(pos);
}

1.5、重载运算符

这样就可以直接使用下标直接访问元素。

    int& operator[](int index)// 可以是返回引用
    {
        return array_[index];
    }

二、完整代码

vector的优点:访问任何一个元素,直接使用下表就行,例如arr[2],速度很快。缺点:删除元素性能开销大。以下给出完整代码:

#include<iostream>

using namespace std;

class MyVector
{
public:
    MyVector();
    ~MyVector();
    void push_back(int value);
    void removeByPose(int pos);
    void removeByValue(int value);
    int find(int value);
    int& operator[](int index)// 可以是返回引用
    {
        return array_[index];
    }
    void show() const;
    void clear()
    {
        size_ = 0;
    }
    bool empty()
    {
        if (array_ == nullptr)
            return true;
        else
            return false;
    }
public:
    int* array_;
    int size_;
    int capacity_;
};
MyVector::MyVector()
{
    size_ = 0;
    capacity_ = 10;
    array_ = new int[capacity_];
}
MyVector::~MyVector()
{
    delete[] array_;
    cout << "free " << array_ << endl;
}
void MyVector::push_back(int value)
{
    if (empty()) return;
    //判断空间是否足够
    if (size_ == capacity_)
    {
        int* newspace = new int[capacity_ * 2]; // 扩容
        memcpy(newspace, array_, capacity_ * sizeof(int));// 备份 - > newsapce
        delete[] array_;// 删除旧空间
        capacity_ *= 2;//扩容
        array_ = newspace;//转移旧空间的值 - > 新空间
    }
    //在末尾插入元素
    array_[size_] = value;
    size_++;
}
void MyVector::show() const
{
    cout << "size_ = " << size_ << " ||";
    for (int i = 0; i < size_; i++)
    {
        cout << array_[i] << " ";
    }
    cout << endl;
}
void MyVector::removeByPose(int pos)
{
    if (empty()) return;
    if (pos < 0 || pos >= size_)//越界
    {
        cout << "out of range!" << endl;
        return;
    }
    for (int i = pos; i < (size_ - 1); i++) //注意越界
    {
        array_[i] = array_[i + 1];
    }
    size_--;
}
int MyVector::find(int value)
{
    if (empty()) return -1;
    int pos = -1;
    for (int i = 0; i < size_; i++)
    {
        if (array_[i] == value)
        {
            pos = i;
            break;
        }
    }
    return pos;
}
void MyVector::removeByValue(int value)
{
    if (empty()) return;
    int pos = find(value);
    if (pos == -1)
    {
        cout << "没有元素:" << value << endl;
        return;
    }
    removeByPose(pos);
}
int main()
{
    MyVector vec;
    for (int i = 0; i < 12; i++)
    {
        vec.push_back(i * i);
    }
    vec.push_back(88);
    vec.show();
    vec.removeByPose(1);
    vec.show();
    vec.removeByPose(2);
    vec.show();
    vec.removeByValue(49);
    vec.show();
    int position = vec.find(25);
    //测试重载
    cout << "test for overload " << endl;
    for (int i = 0; i < vec.size_; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    vec.clear();
    vec.show();
    return 1;
}

下图是执行效果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/141651.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

海康威视(iVMS)综合安防系统任意文件上传漏洞复现 [附POC]

文章目录 海康威视&#xff08;iVMS&#xff09;综合安防系统任意文件上传漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 0x06 修复建议 海康威视&#xff08;iVMS&#xff09;综合安防系统任意文件上传漏洞复…

中国银行模拟器app,用java设计框架,图片网上找的,提供代码,仅供娱乐

回执单生成器的Java程序需要涉及到一些基本的Java编程技能&#xff0c;包括创建类、处理用户输入和格式化输出。下面是一个简单的示例代码&#xff0c;用于生成一个简易的回执单。这个程序将接收用户的输入&#xff0c;然后生成一个格式化的回执单。 请注意&#xff0c;这个示…

解决Chrome无法自动同步书签

前提&#xff1a;&#xff08;要求能正常访问google&#xff09; 准备一个谷歌账号 安装Chrome浏览器 开启集装箱插件&#xff08;或者其他能访问谷歌的工具&#xff09; 步骤&#xff1a;&#xff08;使用集装箱插件/能正常访问谷歌的其他工具&#xff09; 下载安装使用“集…

Databend 开源周报第 119 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 用户案例&#…

故障演练 | 微服务架构下如何做好故障演练

前言 微服务架构场景中&#xff0c;应用系统复杂切分散。长期运行时&#xff0c;局部出现故障时不可避免的。如果发生故障时不能进行有效反应&#xff0c;系统的可用性将极大地降低。 什么是故障演练 故障演练是指模拟生产环境中可能出现的故障&#xff0c;测试系统或应用在…

HTML简单介绍

且视他人之疑目如盏盏鬼火&#xff0c;大胆地去你的夜路。 目录 1.网页 2.Web标准 3.HTML 3.1HTML结构 3.2HTML标签​编辑 4.标签介绍 4.1排版标签 4.2文本格式化标签 4.3媒体标签 4.3.1图片标签 4.3.2 音频标签 4.3.3视频标签 5.相对路径 6.链接标签 6.1target属…

【赠书第5期】AI时代项目经理成长之道:ChatGPT让项目经理插上翅膀

文章目录 前言 1 ChatGPT为项目经理带来便利 2 提供自动化的通知和提醒 3 提供数据分析和可视化 4 结论 5 推荐图书 6 粉丝福利 前言 在现代商业环境中&#xff0c;项目经理需要具备高度的灵活性和响应能力。而现在&#xff0c;随着技术的不断提升和新工具的涌现&#…

大厂设计师必备的8款Sketch插件

每个设计师都渴望有一个高效的插件来提高他们的设计能力。设计插件有助于自动化工作流程&#xff0c;快速组织设计文件或简化内容创建。Sketch可以说是设计师知名的设计工具&#xff0c;特别是其资源社区拥有丰富的Sketch插件&#xff0c;大大提高了设计师的工作效率。本文让设…

打开word文档报错,提示HRESULT 0x80004005 位置: 部分: /word/comments.xml,行: 0,列: 0

某用户遇到这样一个奇怪的问题&#xff0c;就是回复完word的批注后&#xff0c;保存文档再打开就会报错&#xff0c;提示很抱歉&#xff0c;无法打开XXX&#xff0c;因为内容有问题。&#xff0c;详细信息提示HRESULT 0x80004005 位置: 部分: /word/comments.xml,行: 0,列: 0 c…

解释tqdm模块显示进度条:

1. 在Python中&#xff0c;当你使用tqdm模块&#xff08;一个快速、可扩展的Python进度条库&#xff09;时&#xff0c;你可能会看到类似的输出&#xff1a;[6:20:38<6:34:14, 31.25s/it]。 这个输出提供了关于循环进度的详细信息&#xff1a; 6:20:38: 这是已经过去的时…

上海市合成生物产业协会第一届第一次会员大会暨成立仪式今日召开

IFTNews科技讯&#xff1a;11月12日下午&#xff0c;上海市合成生物产业协会第一届第一次会员大会暨成立仪式在上海浦东成功举办。上海市经济和信息化委员会副主任刘平、上海市科学技术委员会一级巡视员兼副主任朱启高、上海市推进科技创新中心建设办公室专职副主任陈尧水出席大…

MySQL:语法速查手册【持续更新...】

一、定义基本表 1、常用的完整性约束 主码约束 primary key外键约束 foreign key唯一性约束 unique非空性约束 not null取值约束 check2、例题 【例1】建立一个“学生”表Student&#xff0c;由学号Sno、姓名Sname、性别Ssex、年龄Sage、所在系Sdept五个属性组成。其中…

面试 | 再也不怕被问 Binder 机制了

Binder 机制 Binder 机制是 Android 特有的一种进程间通信&#xff08;IPC&#xff09;方式 1.1 Binder 机制的作用和原理&#xff1f; Linux系统将一个进程分为用户空间和内核空间。对于进程之间来说&#xff0c;用户空间的数据不可共享&#xff0c;内核空间的数据可共享&a…

【iOS】JSONModel的基本使用

cocoapods的安装和第三方库的配置之前的文章已有涉及&#xff0c;请参考&#xff1a;【iOS】AFNetworking的基本使用和【iOS】Masonry库的基本使用 常规解析JSON数据最基础的方法是使用NSJSONSerialization&#xff0c;见这篇文章【iOS】JSON解析&#xff0c;这样处理数据的方…

文件上传 [SUCTF 2019]CheckIn1

打开题目 我们用cmd curl --head url 查看网站使用的是什么服务器 此题用的是openresty&#xff0c;OpenResty 是一个基于 Nginx 与 Lua 的高性能 Web 平台 我们上传php&#xff0c;phtml的一句话木马都显示不合法 那我们试试传a.jpg的一句话木马 显示我们一句话木马内容里面…

为什么打开idea时,没有启动页面,如何解决?

更新idea2021.2后&#xff0c;当双击idea打开时&#xff0c;发现没有启动界面&#xff0c;直接进入IDEA界面&#xff0c;中间等待时间&#xff0c;让人误以为没有打开idea成功&#xff0c;使得多次点击idea图标。 解决方案就是 在idea界面菜单栏中找到帮助&#xff08;Help)&a…

“新KG”视点 | 王文广——图模互补:知识图谱与大模型的共生新模式

OpenKG 大模型专辑 导读 知识图谱和大型语言模型都是用来表示和处理知识的手段。大模型补足了理解语言的能力&#xff0c;知识图谱则丰富了表示知识的方式&#xff0c;两者的深度结合必将为人工智能提供更为全面、可靠、可控的知识处理方法。在这一背景下&#xff0c;OpenKG组织…

总台农业农村节目中心“金穗行动17联县” 融合传播活动走进河北省高碑店市

强国必先强农&#xff0c;农强方能国强。今年是全面贯彻落实党的二十大精神的开局之年&#xff0c;是全面推进乡村振兴、加快建设农业强国的关键之年。 11月8日&#xff0c;总台农业农村节目中心“金穗行动17联县”融合传播活动走进河北省保定市高碑店市&#xff0c;举办了《CC…

Java-多线程基础篇

前言&#xff1a; 以下是看马老师的视频以及自己阅读《Java多线程编程实战指南》所总结的基础内容&#xff0c;只是个人理解&#xff0c;如有不对还请大家指正。 1.线程的概念&#xff1a; 来自于百度百科&#xff1a;线程是独立调度和分派的基本单位。在Unix System V及Sun…