南昌网站建设过程,孝南区城乡建设局网站,长沙市网站推广公司,wordpress显示相关文章C数据结构与算法 目录
本文前驱课程
1 C自学精简教程 目录(必读)
2 VectorT 动态数组#xff08;模板语法#xff09;
本文目标
1 熟悉迭代器设计模式#xff1b;
2 实现数组的迭代器#xff1b;
3 基于迭代器的容器遍历#xff1b;
迭代器语法介绍
对迭…C数据结构与算法 目录
本文前驱课程
1 C自学精简教程 目录(必读)
2 VectorT 动态数组模板语法
本文目标
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_datam_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::vectorRecord 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 cassertclass 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_holdnullptr;};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_holdnullptr;};//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博客
