2.4 Vector＜T＞ 动态数组（随机访问迭代器）

news/2024/11/23 3:11:00/

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

该 Vector 版本特点

这里的版本主要是使用模板实现、支持随机访问迭代器，支持std::sort等所有STL算法。(本文对随机迭代器的支持参考了 复旦大学 大一公共基础课C++语言的一次作业)

随机访问迭代器的实现主要是继承std::iterator<std::random_access_iterator_tag, T>来实现的。

随机访问迭代器最牛逼的两个接口是：

friend iterator operator+(const iterator& lhs, size_t n);

friend iterator operator-(const iterator& lhs, size_t n);

问题解答

1 为何下面代码中的iterator是struct而不是class？

答：参考struct与class

题目代码

头文件 Vector.h ：

#ifndef VEC_H
#define VEC_H
#include <iostream>
#include <cassert>
#include <initializer_list>
//------下面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------
#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__);
//------上面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------template<typename T>
class Vector
{
public:/* 提供默认构造函数， 否则只能使用有参版本，这会带来不变例如，Vector<int> arr; 这样会报错，因为需要默认构造函数*/Vector(void);//如果类提供了非默认构造函数，编译器不会自动提供默认构造函数Vector(const Vector& from);// 复制构造函数Vector(T* start, T* end);//  非默认构造函数Vector(int count, int value);//2 非默认构造函数Vector(std::initializer_list<T> value_array){for (auto& item : value_array){push_back(item);}}Vector& operator = (const Vector& from);bool operator==(const Vector& other) const{//(1) your codereturn false;}//赋值操作符~Vector();//析构函数
public:size_t size(void) const;bool empty(void) const;T& operator[] (size_t n) const;T& operator[] (size_t n);void push_back(const T& val);void clear(void);
private:void deep_copy_from(const Vector<T>& from);public:struct iterator : std::iterator<std::random_access_iterator_tag, T>{friend class  Vector;friend bool operator == (const iterator& lhs, const iterator& rhs) { return lhs.m_hold == rhs.m_hold; }friend bool operator != (const iterator& lhs, const iterator& rhs) { return !(lhs == rhs); }friend size_t operator - (const iterator& lhs, const iterator& rhs) { return lhs.m_hold - rhs.m_hold; }friend bool operator < (const iterator& lhs, const iterator& rhs) { return lhs.m_hold < rhs.m_hold; }friend bool operator > (const iterator& lhs, const iterator& rhs) { return lhs.m_hold > rhs.m_hold; }friend bool operator <= (const iterator& lhs, const iterator& rhs) { return !(lhs > rhs); }friend bool operator >= (const iterator& lhs, const iterator& rhs) { return !(lhs < rhs); }friend iterator operator + (const iterator& lhs, size_t n) { iterator itr; itr.m_hold = lhs.m_hold + n; return itr; }//随机访问迭代器牛逼的地方friend iterator operator - (const iterator& lhs, size_t n) { iterator itr; itr.m_hold = lhs.m_hold - n; return itr; }//随机访问迭代器牛逼的地方public://用于前置形式iterator& operator++() { m_hold = m_hold + 1; return *this; };iterator& operator--() { m_hold = m_hold - 1; return *this; };//用于后置形式iterator operator++(int) { iterator itr = *this; m_hold += 1; return itr; }iterator operator--(int) { iterator itr = *this; m_hold -= 1; return itr; }T& operator*() const//这里必须是const in C++14{return *m_hold;}private:T* m_hold;};struct const_iterator : std::iterator<std::random_access_iterator_tag, T>{friend class  Vector;friend bool operator == (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold == rhs.m_hold; }friend bool operator != (const const_iterator& lhs, const const_iterator& rhs) { return !(lhs == rhs); }friend size_t operator - (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold - rhs.m_hold; }friend bool operator < (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold < rhs.m_hold; }friend bool operator > (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold > rhs.m_hold; }friend bool operator <= (const const_iterator& lhs, const const_iterator& rhs) { return !(lhs > rhs); }friend bool operator >= (const const_iterator& lhs, const const_iterator& rhs) { return !(lhs < rhs); }friend const_iterator operator + (const const_iterator& lhs, size_t n) { const_iterator itr; itr.m_hold = lhs.m_hold + n; return itr; }//随机访问迭代器牛逼的地方friend const_iterator operator - (const const_iterator& lhs, size_t n) { const_iterator itr; itr.m_hold = lhs.m_hold - n; return itr; }//随机访问迭代器牛逼的地方public://用于前置形式const_iterator& operator++() { m_hold = m_hold + 1; return *this; };const_iterator& operator--() { m_hold = m_hold - 1; return *this; };//用于后置形式const_iterator operator++(int) { const_iterator itr = *this; m_hold += 1; return itr; }const_iterator operator--(int) { const_iterator itr = *this; m_hold -= 1; return itr; }const T& operator*() const{return *m_hold;}private:T* m_hold;};iterator begin() noexcept{iterator itr;itr.m_hold = empty() ? nullptr : &m_data[0];return itr;}const_iterator cbegin() const noexcept;iterator end() noexcept{iterator itr;itr.m_hold = empty() ? nullptr : &m_data[m_size];return itr;}const_iterator cend() const noexcept;
private:size_t m_size = 0;//当前元素数量size_t m_capacity = 0;//容量T* m_data = nullptr;//数据部分
};template<typename T>
Vector<T>::Vector(void)
{
}template<typename T>
Vector<T>::Vector(T * start, T * end)
{std::cout << "Vector(T* start, T* end)" << std::endl;assert(start != nullptr && end != nullptr);m_capacity = m_size = ((size_t)end - (size_t)start)/sizeof(T);//这里如果用int来存放可能会盛不下，size_t可以保证盛放的下assert(m_size > 0);m_data = new T[m_size];for (size_t i = 0; i < m_size; i++){m_data[i] = *start++;}
}
template<typename T>
Vector<T>::Vector(int count, int value)
{std::cout << "Vector(count, value)" << std::endl;if (count <= 0){throw std::runtime_error("size of vector to init must bigger than zero!");}m_data = new T[count];for (size_t i = 0; i < count; i++){m_data[i] = value;}m_capacity = m_size = count;
}
template<typename T>
Vector<T>& Vector<T>::operator=(const Vector<T>& from)
{std::cout << "Vector::operator=" << std::endl;if (this == &from){return *this;}//先释放自己的数据clear();deep_copy_from(from);return *this;
}template<typename T>
Vector<T>::~Vector()
{//(2) your code}
template<typename T>
size_t Vector<T>::size(void) const
{return m_size;
}
template<typename T>
bool Vector<T>::empty(void) const
{//(3) your codereturn false;//此处需要修改。
}
template<typename T>
T& Vector<T>::operator[](size_t n) const
{//(4) your codestatic T t;//此处需要修改。return t;//此处需要修改。
}
template<typename T>
T& Vector<T>::operator[](size_t n)
{//(4) your codestatic T t;//此处需要修改。return t;//此处需要修改。
}
template<typename T>
void Vector<T>::push_back(const T & val)
{//(5) your code// 这里需要考虑第一次插入数据的时候还没有开辟任何动态空间的情况，因为构造函数不再负责事先开辟好少量的初始预留空间了   
}template<typename T>
void Vector<T>::clear(void)
{//(6) your code
}template<typename T>
void Vector<T>::deep_copy_from(const Vector<T>& from)
{//(7) your code}template<typename T>
Vector<T>::Vector(const Vector& from)
{//(8) your code}template<typename T>
typename Vector<T>::const_iterator Vector<T>::cend() const noexcept
{Vector<T>::const_iterator itr;//(9) your codereturn itr;
}template<typename T>
typename Vector<T>::const_iterator Vector<T>::cbegin() const noexcept
{const_iterator itr;//(10) your codereturn itr;
}#endif

测试代码main.cpp：

#include <iostream>
#include <algorithm>
#include "Vector.h"
#include <vector>template<typename T>
void print(const Vector<T>& v, const std::string& msg)
{std::cout << "The contents of " << msg.c_str() << " are:";for (int i = 0; i < v.size(); ++i){std::cout << ' ' << v[i];}std::cout << '\n';
}
template<typename T>
void print_itr(Vector<T>& v, const std::string& msg)
{std::cout << "The contents of " << msg.c_str() << " are:";for (auto itr = v.begin(); itr != v.end(); ++itr){std::cout << ' ' << *itr;}std::cout << '\n';
}
template<typename T>
void print_const_itr(const Vector<T>& v, const std::string& msg)
{std::cout << "The contents of " << msg.c_str() << " are:";for (auto itr = v.cbegin(); itr != v.cend(); ++itr){std::cout << ' ' << *itr;}std::cout << '\n';
}int main()
{Vector<int> a;Vector<int> first;                   // empty vector of intscheck(first.empty() == true && first.size() == 0);Vector<int> second(4, 100);                       // four ints with value 100check(second.empty() == false);check(second.size() == 4);check(*second.begin() == 100);Vector<int> fourth(second);                       // a copy of thirdcheck(fourth.size() == second.size());int myints[] = { 16,2,77,29 };Vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));check(fifth.empty() == false);check(fifth[0] == 16);check(fifth[3] == 29);check(fifth.size() == sizeof(myints) / sizeof(int));print(fifth, "fifth");//The contents of fifth are:16 2 77 29 fifth.push_back(30);check(fifth[4] == 30);check(fifth.size() == 5);print(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 check(fifth.size() == sizeof(myints) / sizeof(int) + 1);first = fifth = fifth;print(first, "first");//The contents of first are:16 2 77 29 30 check(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 std::sort(fifth.begin(), fifth.end());std::cout << "fifith after sort:" << std::endl;print_const_itr(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 Vector<int> a1(myints, myints + sizeof(myints) / sizeof(int));{Vector<int> b(a1);b.push_back(2);check(b[4] == 2);auto result = (b == Vector<int>{ 16, 2, 77, 29, 2});check(result);//iteratorcheck(b.begin() + b.size() == b.end());auto begin = b.begin();auto itr = b.begin() + 1;check(*begin == 16);check(*itr == 2);}{Vector<int> b{ 1,3,5,7 };b.push_back(9);}{Vector<int> c;for (auto i : c){std::cout << i << " ";}c = a1;for (auto i : c){std::cout << i << " ";}std::cout << std::endl;}check(a1.size() == sizeof(myints) / sizeof(int));{Vector<int> c;c = fifth;c[0] = 1;check(c[0] == 1);}
}

预期输出

line:42 Pass
Vector(count, value)
line:44 Pass
line:45 Pass
line:46 Pass
line:48 Pass
Vector(T* start, T* end)
line:52 Pass
line:53 Pass
line:54 Pass
line:55 Pass
The contents of fifth are: 16 2 77 29
line:58 Pass
line:59 Pass
The contents of fifth are: 16 2 77 29 30
line:61 Pass
Vector::operator=
Vector::operator=
The contents of first are: 16 2 77 29 30
line:64 Pass
The contents of fifth are: 16 2 77 29 30
The contents of fifth are: 16 2 77 29 30
fifith after sort:
The contents of fifth are: 2 16 29 30 77
Vector(T* start, T* end)
line:74 Pass
line:76 Pass
Vector::operator=
16 2 77 29
line:95 Pass
Vector::operator=
line:100 Pass
Memory leak report:
No memory leak.


http://www.ppmy.cn/news/1083859.html

相关文章

OpenCV(十七)：拉普拉斯图像金字塔

OpenCV(十七)：拉普拉斯图像金字塔

1.拉普拉斯图像金字塔原理 拉普拉斯图像金字塔是一种多尺度图像表示方法&#xff0c;通过对高斯金字塔进行差分运算得到。它能够提供图像在不同尺度上的细节信息&#xff0c;常用于图像处理任务如图像增强、边缘检测等。 下面是拉普拉斯图像金字塔的原理和步骤&#xff1a; 构…
阅读更多...
软件产品确认测试鉴定测试

软件产品确认测试鉴定测试

软件产品确认测试 确认测试也称鉴定测试&#xff0c;即验证软件的功能、性能及其它特性是否与用户的要求一致。软件确认测试是在模拟的环境下&#xff0c;验证软件是否满足需求规格说明书列出的需求。为此&#xff0c;需要首先制定测试计划&#xff0c;规定要做测试的种类&…
阅读更多...
Lesson4-2:OpenCV图像特征提取与描述---Harris和Shi-Tomas算法

Lesson4-2:OpenCV图像特征提取与描述---Harris和Shi-Tomas算法

学习目标 理解Harris和Shi-Tomasi算法的原理能够利用Harris和Shi-Tomasi进行角点检测 1 Harris角点检测 1.1 原理 H a r r i s Harris Harris角点检测的思想是通过图像的局部的小窗口观察图像&#xff0c;角点的特征是窗口沿任意方向移动都会导致图像灰度的明显变化&#xff…
阅读更多...
MIME类型（Multipurpose Internet Mail Extensions，多用途互联网邮件扩展类型）MultipartFile 多媒体文件上传

MIME类型（Multipurpose Internet Mail Extensions，多用途互联网邮件扩展类型）MultipartFile 多媒体文件上传

目录 MIME媒体类型介绍MediaTypes 有哪些MultipartFile 类介绍MultipartFile 类 接收的文件是二进制嘛代码举例 上传的文件 实现接口 MultipartFile 类有哪些最终调用接口的方法时&#xff0c;会有哪个类实现 如何决定哪个类去实现呢 Spring 会根据运行环境自动选择合适的实现类…
阅读更多...
关于trackformer中的super().forward()

关于trackformer中的super().forward()

代码&#xff1a; import torch import torch.nn as nnclass DETRTrackingBase(nn.Module):def __init__(self):print("build_DETRTrackingBase")def forward(self, x):print("DETRTrackingBase_forward") print(x)x super().forward(x)print(&q…
阅读更多...
使用 htmx 构建交互式 Web 应用

使用 htmx 构建交互式 Web 应用

学习目标&#xff1a;了解htmx的基本概念、特点和用法&#xff0c;并能够运用htmx来创建交互式的Web应用程序。 学习内容&#xff1a; 1. 什么是htmx&#xff1f; - htmx是一种用于构建交互式Web应用程序的JavaScript库。 - 它通过将HTML扩展为一种声明性的交互式语言&a…
阅读更多...
精心整理了优秀的GitHub开源项目，包含前端、后端、AI人工智能、游戏、黑客工具、网络工具、AI医疗等等，空闲的时候方便看看提高自己的视野

精心整理了优秀的GitHub开源项目，包含前端、后端、AI人工智能、游戏、黑客工具、网络工具、AI医疗等等，空闲的时候方便看看提高自己的视野

精心整理了优秀的GitHub开源项目&#xff0c;包含前端、后端、AI人工智能、游戏、黑客工具、网络工具、AI医疗等等&#xff0c;空闲的时候方便看看提高自己的视野。 刚开源就变成新星的 igl&#xff0c;不仅获得了 2k star&#xff0c;也能提高你开发游戏的效率&#xff0c;摆…
阅读更多...
【包过滤防火墙——firewalld动态防火墙】的简单使用

【包过滤防火墙——firewalld动态防火墙】的简单使用

文章目录 firewald与iptables区别firewalld九个区域firewalld配置方法firewalld参数和命令firewalld两种模式firewalld使用实验 firewalld不要与iptables混用 firewald与iptables区别 iptables 主要是基于接口&#xff0c;来设置规则&#xff0c;从而判断网络的安全性。firewa…
阅读更多...
最新文章

Copyright @ 2022~2023