[C++]vector使用和模拟实现

🥁作者: 华丞臧
📕​​​​专栏:【C++】
各位读者老爷如果觉得博主写的不错,请诸位多多支持(点赞+收藏+关注)。如果有错误的地方,欢迎在评论区指出。

推荐一款刷题网站 👉LeetCode


文章目录

  • 一、vector的使用
    • 1.1 常用构造
    • 1.2 迭代器
    • 1.3 容量
    • 1.4 访问元素
    • 1.5 修改元素
  • 二、vector模拟实现
    • 2.1 vector接口
    • 2.2 接口实现
      • 2.2.1 构造和拷贝构造
      • 2.2.2 迭代器
      • 2.2.3 增删元素
        • push_back
        • pop_back
        • insert
        • erase
        • clear
        • swap
      • 2.2.4 访问元素
        • operate[]
      • 2.2.5 容量
        • reserve
        • resize
        • capacity
        • size
        • empty
    • 2.3 测试


一、vector的使用

C++中提供了vector容器,该容器是以连续的空间来存放数据,可以理解为封装过的数组,且这个数组是定义在堆上的。本章介绍一些vector的常用接口,更多的接口使用方法可以参考cplusplus网站。

1.1 常用构造

在这里插入图片描述
C++98中,vector提供了四个构造函数的接口,这些都是比较常用的,operate=也是非常常用的。
实例代码如下:

void Print(vector<int>& v)
{for (auto a : v){cout << a << " ";}cout << endl;
}
void test1()
{vector<int> v1; // 创建一个空对象vector<int> v2(5, 1); // 创建元素类型为int,元素个数为5的vector,并用1进行初始化vector<int> v3(v2.begin(), v2.end()); // 迭代器创建v3vector<int> v4(v3); // 拷贝构造vector<int> v5 = v4; // operate=Print(v1);Print(v2);Print(v3);Print(v4);Print(v5);
}

代码运行结果:
在这里插入图片描述

1.2 迭代器

在这里插入图片描述
迭代器无疑是vector容器较为重要的接口之一了,其中较为常用就是begin和end。有了迭代器后,我们就可以通过迭代器对容器中的数据进行访问读取修改等操作;迭代器隐藏了实现细节提供了统一的使用方式,同时迭代器还是范围for的底层实现。
实例代码如下:

void test2()
{vector<int> v1(10, 0);for (int i = 0; i < 10; i++)v1[i] = i;vector<int>::iterator it = v1.begin();// vector<int>::const_iterator it = v1.cbegin();while (it != v1.end()){cout << *it << " ";++it;}cout << endl;vector<int>::reverse_iterator it2 = v1.rbegin();// vector<int>::const_reverse_iterator it2 = v1.crbegin();while (it2 != v1.rend()){cout << *it2 << " ";++it2;}cout << endl;
}

从实例中可以看到,迭代器的使用方式与指针非常相似,但其实迭代器并不一定是指针。
在这里插入图片描述

1.3 容量

在这里插入图片描述
在vector容器提供的对容量操作的接口中,我们可以使用size查询当前vector容器中有效元素的个数,使用resize来增加有效元素的个数,使用capacity查看vector容器的容量大小,判断vector容器是否为空使用empty,reserve则是用来扩容的。
注意:resize不仅可以扩容,还可以缩容,但是不推荐,缩容会付出很大的代价。
实例代码如下:

void test3()
{vector<int> v;cout << "size: " << v.size() << endl;v.resize(10, 0);int i = 0;for (auto& e : v){cout << e << " ";e = i++;}cout << endl;cout << "size: " << v.size() << endl;v.reserve(100);cout << "capacity: " << v.capacity() << endl;if (v.empty()){cout << "empty" << endl;}else{cout << "nonempty" << endl;}v.resize(5);  // 可以缩容for (auto a : v){cout << a << " ";}cout << endl;cout << "size: " << v.size() << endl;
}

代码运行结果:
在这里插入图片描述

1.4 访问元素

在这里插入图片描述

  • 对于vector来说,访问元素最好用的无疑是[]。在C++中,vector是一个容器,其底层是一段连续的空间类似数组;而[]的重载让vector可以像数组一样使用,只需要提供下标即可访问特定位置上的元素。at与[]类似,获取第n个位置上的元素。
  • front用来获取vector首部元素,返回引用或const引用。
  • back用来获取vector尾部元素,返回引用或const引用。
void test4()
{vector<int> v(10, 0);for (int i = 0; i < 10; i++)v[i] = i;cout << v[5] << endl;cout << "front: " << v.front() << endl;cout << "back: " << v.back() << endl;
}

代码运行结果如下:
在这里插入图片描述

1.5 修改元素

在这里插入图片描述
在官方库提供的修改元素的接口中,常见的接口有push_back、pop_back、insert、erase、swap、clear。不过因为vector实际是一段连续的空间,因此在指定位置插入删除效率极低,通常不会使用,当然还是得看实际需要使用。

二、vector模拟实现

2.1 vector接口

#include <iostream>
#include <assert.h>using namespace std;namespace zch
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;public:iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;public:vector(); template<class InputIterator>vector(InputIterator first, InputIterator last);vector(size_t n, const T& val);vector(long n, const T& val);vector(int n, const T& val);vector(const vector<T>& v);vector<T>& operator=(const vector<T>& v);void push_back(const T& val);void pop_back();iterator insert(iterator pos, const T& val);iterator erase(iterator pos);void reserve(int n);void resize(size_t n, const T& val = 0);size_t capacity() const;size_t size() const;bool empty() const;T& operator[](size_t i) const;~vector();void print();private: iterator _start;  // 头部iterator _finish; // 尾部iterator _endofstorage; // 结束位置,标记容量大小};
}

2.2 接口实现

2.2.1 构造和拷贝构造

在C++98中,vector官方库提供了4种构造函数,分别是空对象构造、迭代器构造、拷贝构造以及给定数量和初始值的构造,那么在我们自己实现的vector中也可以尝试提供这几种构造函数的接口。

需要注意的是给定元素数量和初始值得构造函数,其中用户在传值时元素个数的类型不确定,是否为有符号类型也不确定,因此为了防止传值时发生强制类型转换存在隐患,我们可以每个类型都重载一个接口。

vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{cout << "默认构造" << endl;
}   template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{cout << "迭代器构造" << endl;for(; first != last; ++first){push_back(*first);}
}vector(size_t n, const T& val)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{reserve(n);for(int i = 0; i < n; ++i){push_back(val);}
}vector(long n, const T& val)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{reserve(n);for(int i = 0; i < n; ++i){push_back(val);}
}vector(int n, const T& val)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{reserve(n);for(int i = 0; i < n; ++i){push_back(val);}
}vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{cout << "拷贝构造" << endl;_start = new T[v.capacity()];for(int i = 0; i < v.size(); ++i){_start[i] = v[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();
}

2.2.2 迭代器

前文提到过,vector容器是一种空间连续的容器,因此vector的迭代器实现较为简单,只需要返回其指定位置的指针即可。这里我实现了简单的正向迭代器的const和非const接口,反向迭代器实现较为复杂,需要封装并重载operator++。

public:typedef T* iterator;typedef const T* const_iterator;
public:iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

2.2.3 增删元素

push_back

对于push_back而言,唯一需要注意的就是扩容的问题。我这里采用每次扩容2倍的策略,这样既不会频繁扩容,也不会造成空间浪费。

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()
{assert(!empty());--_finish;
}

insert

insert除了需要注意扩容的问题,还需要注意边界情况下元素插入问题。同时在插入元素时还需要挪动元素,因此insert插入位置越靠近头部效率越低。在官方库中,insert返回一个迭代器类型。

iterator insert(iterator pos, const T& val)
{if(_finish == _endofstorage){size_t len = pos - _start;size_t newCapacity = capacity() == 0? 4 : 2 * capacity();reserve(newCapacity);pos = _start + len;}iterator end = _finish;while(end >= pos + 1){*end = *(end - 1);--end;}*end = val;++_finish;
}

erase

与insert类似的是,erase也需要挪动数据,因此效率也较低,同样erase返回一个迭代器类型。

iterator erase(iterator pos)
{assert(!empty());for(iterator i = pos; i < _finish - 1; ++i){*i = *(i + 1);}--_finish;return pos;
}

clear

在模拟实现的vector中,_start表示首部,_finish表示最后一个有效元素的下一个位置。

void clear()
{_start = _finish;
}

swap

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

2.2.4 访问元素

operate[]

vector重载了[],这样我们使用下标就可以访问并且修改vector当中的元素。

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

2.2.5 容量

reserve

用来扩容,这里实现的reserve不支持缩容,并且只有扩容大小大于原有容量大小才会扩容,一般也不会用到缩容。

void reserve(int n)
{if(n > capacity()){T* start = new T[n];size_t sz = size();if(_start){for(int i = 0; i < sz; ++i){start[i] = _start[i];}}swap(start, _start);_finish = _start + sz;_endofstorage = _start + n;delete[] start;}
}

resize

用来对有效元素的操作,可以进行扩容,与reserve不同,resize会改变对象中有效元素的个数。

void resize(size_t n, const T& val = 0)
{if(n < size()){_finish = _start + n;}else{if(n > capacity()){reserve(n);}while(_finish < _start + n){//push_back(val);*_finish = val;++_finish;}}
}

capacity

获取vector对象容量大小

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

size

获取vector有效元素个数。

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

empty

清空元素。

bool empty() const
{return _start == _finish;
}

2.3 测试

void test1()
{zch::vector<int> a;for(int i = 0; i < 10; ++i){a.push_back(i);}a.print();zch::vector<int> b(10, 5);b.print();a.resize(20);b.resize(5);a.print();b.print();vector<int> c;c.reserve(20);cout << c.size() << " " << c.capacity() << endl;if(c.empty()){cout << "yes" << endl;}else {cout << "no" << endl;}vector<int> d = a; a.insert(a.begin(), 55);b.insert(b.begin() + 5, 55);a.erase(a.begin());a.print();b.print();d.print();
}

程序测试结果如下图所示:
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

无涯教程-Flutter - 简介

Flutter是一个由谷歌开发的开源移动应用软件开发工具包&#xff0c;用于为Android、iOS、 Windows、Mac、Linux、Google Fuchsia开发应用。 通常&#xff0c;创建移动应用程序是一个非常复杂和具有挑战性的任务。有许多框架可用&#xff0c;它提供了开发移动应用程序的出色函数…

Scala入门,idea关联Scala

Scala 介绍 Scala是一种多规范的编程语言&#xff0c;它结合了面向对象编程&#xff08;OOP&#xff09;和函数式编程&#xff08;FP&#xff09;的特征&#xff0c;Scala的名字源于”Scalable language“&#xff0c;意为”可伸缩语言“。2003年开发的&#xff0c;并在JVM&a…

ABB USC329AE01控制器模块

多通道控制&#xff1a; USC329AE01 控制器模块通常具有多个控制通道&#xff0c;可用于监测和控制不同的过程变量。 通讯接口&#xff1a; 这种模块通常支持各种通讯接口&#xff0c;如以太网、串口&#xff08;RS-232、RS-485&#xff09;、Profibus、Modbus 等&#xff0c;…

镜头翻转大师:视频剪辑高手的魔法技巧

在数字媒体时代&#xff0c;视频制作已成为各种规模的组织和个人的必备技能。无论是小型家庭活动还是大型企业项目&#xff0c;都需要通过视频来展示成果、传播信息&#xff0c;或是仅仅为了分享生活的美好瞬间。然而&#xff0c;视频制作并非易事&#xff0c;其中最困难的步骤…

博士后申请有哪些技巧?

在博士后申请过程中&#xff0c;有一些关键的技巧可以帮助申请者提高成功的机会。以下是知识人网小编的一些建议&#xff1a; 1.精选合适的导师和研究课题&#xff1a;选择与自己研究方向相关且感兴趣的导师和课题非常重要。导师的声誉、研究成果和合作风格都会影响你的博士后经…

GNU make系列之介绍Makefile(0)

一.欢迎来到我的酒馆 在本章节介绍Makefile。 目录 一.欢迎来到我的酒馆二.GNU make 预览三.一个简单的Makefile四.make程序如何处理Makefile文件五.在Makefile中使用变量 二.GNU make 预览 2.1 GNU make工具会自动决定哪些程序需要被重新编译&#xff0c;并且执行相应的命令来…

W5100S-EVB-PICO通过SNTP获取网络时间(十一)

前言 上一章我们用开发板进行ping测试&#xff0c;本章我们用它通过SNTP获取网络时间并在串口显示。 什么是SNTP? 能用来做什么? SNTP(Simple Network Time Protocal简单网络时间协议)&#xff0c;用于跨广域网或局域网同步时间的协议&#xff0c;具有较高的精确度&#xff…

Python爬虫:一个爬取豆瓣电影人像的小案例

从谷歌浏览器的开发工具进入 选择图片右键点击检查 ![在这里插入图片描述](https://img-blog.csdnimg.cn/1b38c2a942c441fb8cb545a28bb35015.png 翻页之后发现网址变化的只有start数值&#xff0c;每次变化值为30 Python代码 import requests from bs4 import BeautifulSou…

C++11

✅<1>主页&#xff1a;&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;C11 ☂️<3>开发环境&#xff1a;Visual Studio 2022 &#x1f4ac;<4>前言&#xff1a;C标准10年磨一剑,成就了一次非常成功的更新C11&#xff0c;增加了非常有…

DolphinDB 携手白鲸开源 WhaleStudio 打造高效敏捷的 DataOps 解决方案

浙江智臾科技有限公司&#xff08;简称&#xff1a;DolphinDB&#xff09;和北京白鲸开源科技有限公司&#xff08;简称&#xff1a;白鲸开源&#xff09;是在大数据技术领域活跃的两支专业团队。 DolphinDB 专注于为用户提供集高性能存储、复杂分析能力和流处理于一体的实时计…

三、原型模式

一、什么是原型模式 原型&#xff08;Prototype&#xff09;模式的定义如下&#xff1a;用一个已经创建的实例作为原型&#xff0c;通过复制该原型对象来创建一个和原型相同或相似的新对象。在这里&#xff0c;原型实例指定了要创建的对象的种类。用这种方式创建对象非常高效&a…

2023固态U盘、移动硬盘对比

最近测试了几款固态U盘/移动硬盘&#xff0c;希望能大家的选购有点帮助。 1、移速逸动-2T&#xff08;500MB/s&#xff09;&#xff1a;799元某音 2、爱国者u397-1T&#xff08;1000MB/s&#xff09;&#xff1a;578元京东 3、梵想FF520-512G&#xff08;500MB/s&#xff09…

【数据结构】多叉树转换为二叉树-c++代码实现-POJ 3437 Tree Grafting

文章目录 写这个题目的原因寻找提交网址题目解决思路AC代码成功AC 写这个题目的原因 1、今天在看王道考研数据结构的课&#xff08;虽然我要保研&#xff0c;但是因为这些看保研面试的时候会问&#xff0c;所以看一下嘞orz&#xff09;&#xff0c;看到了这个多叉树转换为二叉…

QT基础教程之六布局管理器和常用控件

QT基础教程之六布局管理器和常用控件 布局管理器 所谓 GUI 界面&#xff0c;归根结底&#xff0c;就是一堆组件的叠加。我们创建一个窗口&#xff0c;把按钮放上面&#xff0c;把图标放上面&#xff0c;这样就成了一个界面。在放置时&#xff0c;组件的位置尤其重要。我们必须…

1、Spring是什么?

Spring 是一款主流的 Java EE 轻量级开源框架 。 框架 你可以理解为是一个程序的半成品&#xff0c;它帮我们实现了一部分功能&#xff0c;用这个框架我们可以减少代码的实现和功能的开发。 开源 也就是说&#xff0c;它开放源代码。通过源代码&#xff0c;你可以看到它是如何…

不需要任何编程经验也能牢固掌握Java精髓——《Java官方入门教程(第9版·Java 17)》

《Java官方入门教程&#xff08;第9版Java 17&#xff09;》针对Java SE 17做了全面细致的更新&#xff0c;将引导你轻松学习最新的核心Java编程技能。《Java官方入门教程&#xff08;第9版Java 17&#xff09;》由畅销编程书作者Herbert Schildt撰写&#xff0c;开篇讲述基础知…

Java实现根据商品ID获取当当商品详情数据,当当商品详情数据接口,当当网API接口封装方法

要通过当当网的API获取商品详情数据&#xff0c;您可以使用当当开放平台提供的接口来实现。以下是一种使用Java编程语言实现的示例&#xff0c;展示如何通过当当开放平台API获取商品详情属性数据接口&#xff1a; 首先&#xff0c;确保您已注册成为当当网开放平台的开发者&…

C位运算做标识位使用

C位运算做标识位使用

Keil模拟器 STM32F103上手

一般嵌入式操作系统因为它的特殊性&#xff0c;往往和硬件平台密切相关连&#xff0c;具体的嵌入式操作系统往往只能在特定的硬件上运行。 可以采用软件方式来模拟一个能够运行RT-Thread操作系统的硬件模块&#xff0c;这就是ARM公司的MDK-ARM仿真模拟环境。 MDK-ARM&#xf…

Spring Boot+Atomikos进行多数据源的分布式事务管理详解和实例

文章目录 0.前言1.参考文档2.基础介绍3.步骤1. 添加依赖到你的pom.xml文件:2. 配置数据源及其对应的JPA实体管理器和事务管理器:3. Spring BootMyBatis集成Atomikos4. 在application.properties文件中配置数据源和JPA属性&#xff1a; 4.使用示例5.底层原理 0.前言 背景&#x…