Vector 动态数组（迭代器）

C++数据结构与算法 目录

本文前驱课程

1 C++自学精简教程 目录(必读)

2 Vector<T> 动态数组（模板语法）

本文目标

1 熟悉迭代器设计模式；

2 实现数组的迭代器；

3 基于迭代器的容器遍历；

迭代器语法介绍

对迭代器的详细介绍参考 ： 迭代器 iterator 范围for循环 删除容器的元素 remove erase

迭代器的能力

迭代器的功能

迭代器实际上是一个内部类。通过下面的迷你代码，我们可以看到迭代器应该具备的能力。

class Vector
{
public:class Iterator{};Iterator begin() {Iterator itr;/* (1)开始迭代器要能指向第一个元素 m_data[0]*/return itr;};Iterator end(){Iterator itr;/* (2)结束迭代器指向空最后一个元素的下一个位置 m_data+m_size */return itr;};int& operator*();// 重载解引用操作符重载：让迭代器可以通过解引用得到其指向变量的引用  *itr = 5;iterator & operator++(); //用于前置形式  ++itr;int* m_data;//存储动态内存int m_size;
};int main()
{Vector arr;auto itr = arr.begin();for (auto itr = arr.begin(); itr != arr.end()/* (3)迭代器要能够比较相等*/; itr++/* (4)迭代器要能够移动到下一个位置 */ ){cout << *itr/* (5)迭代器要能够解引用得到容器的元素*/ << " ";}return 0;
}

迭代器的实现

现在我们考虑如何实现这种能力。

对于动态数组Vector来说：

(1)开始迭代器要能指向第一个元素 m_data[0]：可以给迭代器添加一个构造函数，传递动态数组的首元素地址给迭代器。

(2)结束迭代器指向空最后一个元素的下一个位置：可以给迭代器的构造函数传入动态数组首地址偏移 m_size 个元素后的地址。m_data + m_size

(3)迭代器要能够比较相等：让迭代器重载， 等于操作符 == 不等于操作符 !=

(4)迭代器要能够移动到下一个位置：让迭代器重载自增操作符 ++

(5)迭代器要能够解引用得到容器的元素：让迭代器重载解引用操作符 *

至此，迭代器的功能就全部实现完成了。

完整测试用例

//------下面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------
#include <algorithm>
#include <cstdlib>
#include <iostream> 
#include <vector>
#include <utility>
using namespace std;
struct Record { Record(void* ptr1, size_t count1, const char* location1, int line1, bool is) :ptr(ptr1), count(count1), line(line1), is_array(is) { int i = 0; while ((location[i] = location1[i]) && i < 100) { ++i; } }void* ptr; size_t count; char location[100] = { 0 }; int line; bool is_array = false; bool not_use_right_delete = false; }; bool operator==(const Record& lhs, const Record& rhs) { return lhs.ptr == rhs.ptr; }std::vector<Record> myAllocStatistic; void* newFunctionImpl(std::size_t sz, char const* file, int line, bool is) { void* ptr = std::malloc(sz); myAllocStatistic.push_back({ ptr,sz, file, line , is }); return ptr; }void* operator new(std::size_t sz, char const* file, int line) { return newFunctionImpl(sz, file, line, false); }void* operator new [](std::size_t sz, char const* file, int line)
{ return newFunctionImpl(sz, file, line, true); }void operator delete(void* ptr) noexcept { Record item{ ptr, 0, "", 0, false }; auto itr = std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr != myAllocStatistic.end()) { auto ind = std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr = nullptr; if (itr->is_array) { myAllocStatistic[ind].not_use_right_delete = true; } else { myAllocStatistic[ind].count = 0; }std::free(ptr); } }void operator delete[](void* ptr) noexcept {Record item{ ptr, 0, "", 0, true }; auto itr = std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr != myAllocStatistic.end()) { auto ind = std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr = nullptr; if (!itr->is_array) { myAllocStatistic[ind].not_use_right_delete = true; } else { myAllocStatistic[ind].count = 0; }std::free(ptr); }}
#define new new(__FILE__, __LINE__)
struct MyStruct { void ReportMemoryLeak() { std::cout << "Memory leak report: " << std::endl; bool leak = false; for (auto& i : myAllocStatistic) { if (i.count != 0) { leak = true; std::cout << "leak count " << i.count << " Byte" << ", file " << i.location << ", line " << i.line; if (i.not_use_right_delete) { cout << ", not use right delete. "; }	cout << std::endl; } }if (!leak) { cout << "No memory leak." << endl; } }~MyStruct() { ReportMemoryLeak(); } }; static MyStruct my; void check_do(bool b, int line = __LINE__) { if (b) { cout << "line:" << line << " Pass" << endl; } else { cout << "line:" << line << " Ohh! not passed!!!!!!!!!!!!!!!!!!!!!!!!!!!" << " " << endl; exit(0); } }
#define check(msg)  check_do(msg, __LINE__);
//------上面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------#include <iostream>
#include <cassert>class Vector
{
public:Vector(void);//1 默认构造函数Vector(int count, int value);//2 非默认构造函数Vector(const Vector& from);//4 复制构造函数Vector(int* start, int* end);// 3 非默认构造函数Vector& operator = (const Vector& from);~Vector();
public:size_t size(void) const;bool empty(void) const;const int& operator[] (size_t n) const;int& operator[] (size_t n);void push_back(const int& val);
public:class iterator{friend class  Vector;friend bool operator == (const iterator& lhs, const iterator& rhs);//用于实现!=,因为==非常容易实现friend bool operator != (const iterator& lhs, const iterator& rhs);public:iterator & operator++(); //用于前置形式iterator operator++(int); //用于后置形式，这里有个int参数纯粹是为了区分前自增操作符而加的语法规定int& operator*();//解引用操作符重载private:int* m_hold=nullptr;};class const_iterator{friend class  Vector;public:bool operator == (const const_iterator& rhs) { return this->m_hold == rhs.m_hold; }//用于实现!=,因为==非常容易实现bool operator != (const const_iterator& rhs) { return !(*this == rhs); };const_iterator & operator++(); //用于前置形式 ++itr  先改变自己，指向下一个位置，再返回自己const_iterator operator++(int); //用于后置形式 itr++ 先创建一个改变前的副本用于返回，再在返回前改变自己，指向下一个位置const int& operator*() const;private:const int* m_hold=nullptr;};//noexcept 表示这个函数内不会抛出异常，这样有助于编译器优化代码生成const_iterator begin() const noexcept;iterator begin() noexcept;const_iterator end() const noexcept;iterator end() noexcept;
private:void clear(void);
private:size_t m_size;//当前元素数量size_t m_capacity;//容量int* m_data;//数据部分
};
Vector::Vector(void):m_data(nullptr), m_size(0), m_capacity(0)
{std::cout << "Vector()" << std::endl;
}Vector::Vector(const Vector& from)
{if (from.empty()){m_data = nullptr;m_size = 0;m_capacity = 0;return;}m_capacity = m_size = from.m_size;m_data = new int[m_size];for (auto i = 0; i < m_size; ++i){m_data[i] = from.m_data[i];}std::cout << "Vector(const Vector & from)" << std::endl;
}Vector::Vector(int count, int value): m_data(nullptr)
{if (count <= 0){throw std::runtime_error("size of vector to init must bigger than zero!");}m_data = new int[count];for (size_t i = 0; i < count; i++){m_data[i] = value;}m_capacity = m_size = count;std::cout << "Vector(const, value)" << std::endl;
}Vector::Vector(int* start, int* end): m_data(nullptr), m_size(0), m_capacity(0)
{assert(start != nullptr && end != nullptr);m_capacity = m_size = ((size_t)end - (size_t)start) / sizeof(int);//这里如果用int来存放可能会盛不下，size_t可以保证盛放的下assert(m_size > 0);m_data = new int[m_size];for (size_t i = 0; i < m_size; i++){m_data[i] = *start++;}std::cout << "Vector(start, end)" << std::endl;
}Vector& Vector::operator=(const Vector& from)
{if (this == &from){return *this;}//先释放自己的数据clear();m_size = from.m_size;m_capacity = from.m_capacity;m_data = new int[m_size];for (size_t i = 0; i < m_size; i++){m_data[i] = from.m_data[i];}return *this;std::cout << "Vector & Vector::operator=(const Vector & from)" << std::endl;
}Vector::~Vector()
{if (m_data){delete[] m_data;}std::cout << "~Vector()" << std::endl;
}size_t Vector::size(void) const
{return m_size;
}bool Vector::empty(void) const
{return m_size == 0;
}const int& Vector::operator[](size_t n) const
{return m_data[n];
}int& Vector::operator[](size_t n)
{return  m_data[n];
}void Vector::push_back(const int& val)
{if (m_capacity > m_size)//直接追加到最后一个{m_data[m_size++] = val;}else//只有满了的那一瞬间，才翻倍开辟新空间{auto pNewArray = new int[m_capacity = m_capacity + m_capacity];//拷贝老数据for (size_t i = 0; i < m_size; i++){pNewArray[i] = m_data[i];}//追加最新的末尾元素pNewArray[m_size++] = val;delete[] m_data;m_data = pNewArray;}
}
//下面的代码 函数名是 Vector::begin
//           返回值类型是 Vector::const_iterator
//返回值类型之所以要加类作用域是因为，返回值类型在函数作用域之外。这是由C语言继承而来的
Vector::const_iterator Vector::begin() const noexcept
{if (empty()){return end();}const_iterator itr;//(1) your code 下面的代码仅仅是让编译通过，可能需要你重新实现return itr;
}Vector::iterator Vector::begin() noexcept
{if (empty()){return end();}iterator itr;//(1) your code 下面的代码仅仅是让编译通过，可能需要你重新实现return itr;
}Vector::const_iterator Vector::end() const noexcept
{const_iterator itr;//(2) your code 下面的代码仅仅是让编译通过，可能需要你重新实现// 如果容器为空，不能返回下标返回的元素位置return itr;
}Vector::iterator Vector::end() noexcept
{iterator itr;//(2) your code 下面的代码仅仅是让编译通过，可能需要你重新实现// 如果容器为空，不能返回下标返回的元素位置return itr;
}void Vector::clear(void)
{//(3) your code 下面的代码仅仅是让编译通过，可能需要你重新实现}bool operator==(const Vector::iterator& lhs, const Vector::iterator& rhs)
{//(4) your code 下面的代码仅仅是让编译通过，可能需要你重新实现return false;
}bool operator!=(const Vector::iterator& lhs, const Vector::iterator& rhs)
{//(5) your code 下面的代码仅仅是让编译通过，可能需要你重新实现return false;
}Vector::iterator& Vector::iterator::operator++()
{//(6) your code 下面的代码仅仅是让编译通过，可能需要你重新实现return *this;
}
Vector::const_iterator& Vector::const_iterator::operator++()
{//(7) your code 下面的代码仅仅是让编译通过，可能需要你重新实现return *this;
}Vector::iterator Vector::iterator::operator++(int)
{//(8) your code 下面的代码仅仅是让编译通过，可能需要你重新实现return iterator();
}
Vector::const_iterator Vector::const_iterator::operator++(int)
{return Vector::const_iterator();
}
int& Vector::iterator::operator*()
{//(9) your code 下面的代码是错误的！不可以返回临时变量的引用！仅仅是让编译通过，需要你重新实现int a = 0; return a;
}
const int& Vector::const_iterator::operator*() const
{//(9) your code 下面的代码是错误的！不可以返回临时变量的引用！仅仅是让编译通过，需要你重新实现int a = 0;return a;
}
void print(const Vector& v, const std::string& msg)
{std::cout << "print The contents of " << msg.c_str() << " are:";for (int i = 0; i < v.size(); ++i){std::cout << ' ' << v[i];}std::cout << '\n';
}
void print_itr(Vector& v, const std::string& msg)
{std::cout << "print_itr The contents of " << msg.c_str() << " are:";for (auto itr = v.begin(); itr != v.end(); ++itr){std::cout << ' ' << *itr;}std::cout << '\n';
}
void print_const_itr(const Vector& v, const std::string& msg)
{std::cout << "print_const_itr The contents of " << msg.c_str() << " are:";for (auto itr = v.begin(); itr != v.end(); ++itr){//*itr = 4;std::cout << ' ' << *itr;}std::cout << '\n';
}int main()
{Vector a;Vector first;                   // empty vector of intsassert(first.empty() == true && first.size() == 0);Vector second(4, 100);                       // four ints with value 100assert(second.empty() == false);assert(second.size() == 4);assert(*second.begin() == 100);Vector fourth(second);                       // a copy of thirdassert(fourth.size() == second.size());int myints[] = { 16,2,77,29 };Vector fifth(myints, myints + sizeof(myints) / sizeof(int));assert(fifth.empty() == false);assert(fifth[0] == 16);assert(fifth[3] == 29);assert(fifth.size() == sizeof(myints) / sizeof(int));print(fifth, "fifth");//The contents of fifth are:16 2 77 29 fifth.push_back(30);assert(fifth[4] == 30);assert(fifth.size() == 5);print(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 assert(fifth.size() == sizeof(myints) / sizeof(int) + 1);first = fifth = fifth;print(first, "first");//The contents of first are:16 2 77 29 30 assert(first.empty() == false && first.size() == fifth.size());print_itr(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 print_const_itr(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 Vector a1(myints, myints + sizeof(myints) / sizeof(int));{Vector b(a1);b.push_back(2);assert(b[4] == 2);}{Vector c;for (auto i : c){std::cout << i << " ";}c = a1;a1 = c;c = a1;for (auto i : c){std::cout << i << " ";}std::cout << std::endl;}assert(a1.size() == sizeof(myints) / sizeof(int));{Vector c;c = fifth;c[0] = 1;assert(c[0] == 1);}
}

期待输出：

祝你好运！

答案在此

C++数据结构与算法（全部答案）_数据结构与算法c++版答案_C++开发者的博客-CSDN博客

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

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

相关文章

java入门第三节

java入门第三节

java入门第三节 一.什么是oop 1.pop与oop (1).面向过程编程&#xff1a;&#xff08;POP&#xff1a;Procedure Oriented Programming&#xff09; 1.步骤清晰简单&#xff0c;第一步做什么&#xff0c;第二步做什么&#xff0c;按照顺序&#xff1b; 2.代码线性&#xff0…
阅读更多...
一个简单的vim例子

一个简单的vim例子

一.欢迎来到我的酒馆 在本章节介绍vim工具。 目录 一.欢迎来到我的酒馆二.什么是vim三.开始使用vim 二.什么是vim 2.1什么是vim vim是一种Linux命令行类型的文本编辑器。vim指的是"vi improved"&#xff0c;意思是vi工具的升级版。vim是基于vi实现的&#x…
阅读更多...
Scrum Master 面试问题- ChatGPT 版

Scrum Master 面试问题- ChatGPT 版

之前&#xff0c;我测试了 ChatGPT 如何回答《Scrum Master 面试指南》中的问题&#xff1b;见下文。早在2023 年 1 月&#xff0c;我就不会在 Scrum Master 面试过程中采取下一步&#xff0c;邀请ChatGPT与几名Scrum团队成员进行全方位的面试。 那么&#xff0c;如果 GPT 3.5…
阅读更多...
【安全】原型链污染 - Hackit2018

【安全】原型链污染 - Hackit2018

目录 准备工作 解题 代码审计 Payload 准备工作 将这道题所需依赖模块都安装好后 运行一下&#xff0c;然后可以试着访问一下&#xff0c;报错是因为里面没内容而已&#xff0c;不影响,准备工作就做好了 解题 代码审计 const express require(express) var hbs require…
阅读更多...
考生作弊行为分析算法

考生作弊行为分析算法

考生作弊行为分析系统利用pythonyolo系列网络模型算法框架&#xff0c;考生作弊行为分析算法利用图像处理和智能算法对考生的行为进行分析和识别&#xff0c;经过算法服务器的复杂计算和逻辑判断&#xff0c;算法将根据考生行为的特征和规律&#xff0c;判定是否存在作弊行为。…
阅读更多...
appium+python自动化测试

appium+python自动化测试

获取APP的包名 1、aapt即Android Asset Packaging Tool&#xff0c;在SDK的build-tools目录下。该工具可以查看apk包名和launcherActivity 2、在android-sdk里面双击SDK-manager,下载buidl-tools 3、勾选build-tools&#xff0c;随便选一个版本&#xff0c;我这里选的是24的版…
阅读更多...
windows Etcd的安装与使用

windows Etcd的安装与使用

一、简介 etcd是一个分布式一致性键值存储&#xff0c;其主要用于分布式系统的共享配置和服务发现。 etcd由Go语言编写 二、下载并安装 1.下载地址&#xff1a; https://github.com/coreos/etcd/releases 解压后的目录如下&#xff1a;其中etcd.exe是服务端&#xff0c;e…
阅读更多...
Sublime Text汉化，主打简单明了

Sublime Text汉化，主打简单明了

在Sublime中设置中文的步骤如下&#xff1a; 1.打开Sublime Text&#xff0c;使用快捷键ShiftCtrlP&#xff08;MacOS下cmdShiftP&#xff09;&#xff0c;弹出查找栏。 2.在搜索框中输入关键字"install"&#xff0c;出现下拉选项&#xff0c;点击选择其中的"P…
阅读更多...
程序与进程

程序与进程

一、程序是怎么被执行的 1.在程序中&#xff0c;由引导代码去调用程序中得main函数&#xff0c;而这个过程由链接器完成&#xff0c;链接器将引导代码链接到我们的应用程序构成可执行文件。 2.程序运行需要通过操作系统的加载器来实现&#xff0c;加载器是操作系统中的程序&a…
阅读更多...
IDEA maven上传速度很慢、解决办法

IDEA maven上传速度很慢、解决办法

maven上传的速度很慢&#xff0c;排除网络原因&#xff0c;需要检查配置 一、项目配置 以下针对于maven仓库不在C盘的情况&#xff1a; File | Settings | Build, Execution, Deployment | Build Tools | Maven 以IDEA为例&#xff0c;打开 File&#xff08;文件&#xff09;…
阅读更多...
iOS - 资源按需加载 - ODR

iOS - 资源按需加载 - ODR

一、瘦身技术大图 二、On-Demand Resources 简介 将其保存管理在苹果的服务器&#xff0c;按需使用资源、优化包体积&#xff0c;实现更小的应用程序。ODR 的好处&#xff1a; 应用体积更小&#xff0c;下载更快&#xff0c;提升初次启动速度资源会在后台下载操作系统将会在磁…
阅读更多...
酒店的业务高度，关键还得看这个技术！

酒店的业务高度，关键还得看这个技术！

在酒店业务中&#xff0c;资产管理系统的重要性不容忽视。在这个竞争激烈且日益复杂的行业中&#xff0c;酒店经营者需要精确而高效地管理各种资源&#xff0c;包括客房、设备、财务以及人力。 资产管理系统为管理者提供了一个集中管理、优化和监控资产的强大工具。这不仅有助于…
阅读更多...
【AI模型】LibTorch深度学习框架配置与使用

【AI模型】LibTorch深度学习框架配置与使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍LibTorch深度学习框架配置与使用。 学其所用&#xff0c;用其所学。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下次…
阅读更多...
机器学习：异常检测实战

机器学习：异常检测实战

文章目录 Anomaly Detection目录任务介绍数据集方法评估Baseline报告报告评价标准 Anomaly Detection 目录 任务介绍 无监督的异常检测 数据集 方法 autoencode 是否能够还原出原始类型图片&#xff0c;基于重构loss来判断是否正常 重构误差当作异常分数 评估 采用ROC和AUC…
阅读更多...
0202hdfs的shell操作-hadoop-大数据学习

0202hdfs的shell操作-hadoop-大数据学习

文章目录 1 进程启停管理2 文件系统操作命令2.1 HDFS文件系统基本信息2.2 介绍2.3 创建文件夹2.4 查看指定文件夹下的内容2.5 上传文件到HDFS2.6 查看HDFS文件内容2.7 下载HDFS文件2.8 HDFS数据删除操作 3 HDFS客户端-jetbrians产品插件3.1 Big Data Tools 安装3.2 配置windows…
阅读更多...
MySQL数据库 索引、事务、储存引擎

MySQL数据库 索引、事务、储存引擎

索引 索引的概念 索引是一个排序的列表&#xff0c;在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址&#xff08;类似于C语言的链表通过指针指向数据记录的内存地址&#xff09;。 使用索引后可以不用扫描全表来定位某行的数据&#xff0c;而是先通过索引表找…
阅读更多...
[C++]vector使用和模拟实现

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

&#x1f941;作者&#xff1a; 华丞臧 &#x1f4d5;​​​​专栏&#xff1a;【C】 各位读者老爷如果觉得博主写的不错&#xff0c;请诸位多多支持(点赞收藏关注)。如果有错误的地方&#xff0c;欢迎在评论区指出。 推荐一款刷题网站 &#x1f449;LeetCode 文章目录 一、vec…
阅读更多...
无涯教程-Flutter - 简介

无涯教程-Flutter - 简介

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

Scala入门，idea关联Scala

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

ABB USC329AE01控制器模块

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

Copyright @ 2022~2023