分块刨析从函数原型到分块实现C++STL(vector)

2024-02-20 23:10

本文主要是介绍分块刨析从函数原型到分块实现C++STL(vector),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一, 函数原型部分分析(简单举例使用便于理解)

二、 迭代器设计思想,vector迭代器分析

三,整体的大体可以快速看见效果的框架

三,重点函数分块分析图解实现, 仅仅只是写哪些可能大家不清楚的,都可以写的部分写了也没用

各种构造函数的设计思想,如何只写一个然后实现代码复用

区间范围range构造

拷贝构造

赋值重载

移动构造   (更加强盗,不齿,直接抢将死之人的身份)

insert  +  erase 的设计,以及分析返回值,加之分析迭代器失效会出现的位置,和抛出设计中的细节之处

insert

erase

四. 整体代码  (实现代码)

五. 整合小结一下,以及特别谈一谈如何写一个STL容器和迭代器设计思想(迭代器是什么),迭代器失效的问题.

如何实现一个STL书写的方法论


一, 函数原型部分分析(简单举例使用便于理解)

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  • 简单测试使用:
int main() {std::vector<int> vint;vint.reserve(3);cout << vint.capacity() << endl;vint.resize(10, 5);cout << vint.size() << endl;for (auto& e : vint) {cout << e << " ";}cout << endl;return 0;
}

666681ca65714004a7feca96c4e216f7.png

 如上可以证明的就是resize改变的size ,reserve改变的是capacity是预先开出空间,至于使用reserve的使用可以减少扩容的次数.. 提高效率..

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  •  迭代器函数, 返回迭代器. 支持迭代器, 有了迭代器才能支持范围的遍历方式. 像是上述使用的for (aoto& e : vint) 的遍历方式都是因为存在迭代器作为支撑才可以的
  • 为了验证, 简单的使用迭代器模板类模拟实现一下  for_each
  • 引入一下小小的知识点,迭代器类型   +   仿函数类型   作为类型模板是一种很常见的使用方式.    这种方式常用在对于一段区间的元素做函数处理的场景下:  (很重要的trait)
  • template<class InputIterator, class Function>void Func(InputIterator first, InputIterator last, Function f) {while (first != last) {f(*first);++first;}return;}

    eg :      watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

template<class T >struct Print {void operator()(T& val)const {cout << val << " ";}};template<class InputIterator, class Function>void for_each(InputIterator first, InputIterator last, Function f) {while (first != last) {f(*first);++first;}return;}
}int main() {std::vector<int> vint;vint.reserve(3);cout << vint.capacity() << endl;vint.resize(10, 5);cout << vint.size() << endl;//for (auto& e : vint) {//	cout << e << " ";//}tyj::for_each(vint.begin(), vint.end(), tyj::Print<int>());cout << endl;return 0;
}
  •  所以可以证明的是for(aoto& e : 容器)的这种遍历方式应该底层也是基于迭代器实现的

二、 迭代器设计思想,vector迭代器分析

  • 迭代器的有点像是指针指针. 可以是一个类,甚至可以是原生指针. 他是可以支持 ++  --  -> 和 * 运算符重载的一个类, 或者说是原生指针.
  • 因为  vector 的底层就是一个动态数组.维护的是一个线性空间,  所以普通的原生指针可以直接使用做迭代器, 因为本身指针就是支持operator++  operator-- operator*这些运算的
		typedef T* iterator;typedef const T* const_iterator;

三,整体的大体可以快速看见效果的框架

  • 对于上述先解释一下,很多时候我们要写一个很大的东西, 为了降低deBug的成本, 其实可以先实现必要性的可以看见效果的区块, 大体的框架性写好, 效果看到了然后
  • 插入元素时候的扩容机制: 如果是需要扩容,采取的一般是二倍扩容的方式进行扩容的,扩容分为三部,新开空间,转移数据,销毁原有空间...      (记住转移数据调用深拷贝,不可以memcpy) why?

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

 watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

namespace tyj {template <class T>class vector {typedef T* iterator;typedef const T* const_iterator;public:vector() //默认构造: start(nullptr), finish(nullptr), end_of_storage(nullptr) {}vector(int n, const T& val = T()) //带参构造: start(new T[n]) {finish = start + n;end_of_storage = finish;for (int i = 0; i < n; ++i) {start[i] = val;}}iterator begin() {return start;}const_iterator begin() const {return start;}iterator end() {return finish;}const_iterator end() const {return finish - 1;}size_t size() const {return finish - start;}size_t capacity() const {return end_of_storage - start;}void reserve(int n) {//预先开空间if (n <= capacity()) return;//说明需要新开空间, 三步//1.新开空间T* pTemp = new T[n];//2.转移数据int _size = size();for (int i = 0; i < _size; ++i) {pTemp[i] = start[i];}//3.销毁原有空间delete[] start;start = pTemp;finish = start + _size;end_of_storage = start + n;}void push_back(const T& val) {if (size() == capacity()) {reserve(size() == 0 ? 8 : (size() << 1));}//放入数据*finish = val;finish++; //尾部迭代器后移}private://[start, finish)iterator start;//当前使用空间起点iterator finish;//当前使用空间末尾iterator end_of_storage; //空间末尾};template <class T >struct Print {void operator()(T& val) const {cout << val << " ";}};template<class InputIterator, class Function>void for_each(InputIterator first, InputIterator last, Function f) {while (first != last) {f(*first);++first;}}
}int main() {tyj::vector<int> vint;for (int i = 0; i < 5; ++i)vint.push_back(i);cout << vint.size() << endl;tyj::for_each(vint.begin(), vint.end(), tyj::Print<int>());cout << endl;return 0;
}

b1f4e9b4d64347bca7c9bb2f384ba7bc.png

三,重点函数分块分析图解实现, 仅仅只是写哪些可能大家不清楚的,都可以写的部分写了也没用

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  •  然后就是一个一个函数的分析应该如何设计的问题

各种构造函数的设计思想,如何只写一个然后实现代码复用

  • 区间范围range构造

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  • swap为复用代码做准备

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  • 拷贝构造

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  • 赋值重载

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

同样的道理,已经复用了拷贝构造函数构造出来了  vec 对象直接  窃取  vec 换成自己的,马匪看过吗,让我成为你, 你成为空气 

  • 移动构造   (更加强盗,不齿,直接抢将死之人的身份)

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

insert  +  erase 的设计,以及分析返回值,加之分析迭代器失效会出现的位置,和抛出设计中的细节之处

  • insert

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  • erase

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

  • 再看   insert   +  erase   都存在一个  iterator作为返回值,为啥,跟新旧的迭代器,防止迭代器失效。。。   向如下的代码为啥要  接收一下  erase 之后的返回值也就可以理解了,防止使用失效的迭代器
  • void test() {std::vector<int> vec(5, 1);for (auto it = vec.begin(); it != vec.end(); ++it) {it = vec.erase(it);}
    }it = v.begin();
    PrintVector(v);
    while (it != v.end()) {if (*it % 2 == 0)it = v.erase(it);else++it;
    }
  • 至此比较有用的部分都已经分析完成了。

四. 整体代码  (实现代码)

#include <vector> 
#include <algorithm>
#include <iostream>
#include <assert.h>
using namespace std;namespace tyj {template <class T >class vector {public://原生指针作为迭代器typedef T* iterator;typedef const T* const_iterator;//无参构造函数vector(): start(nullptr), finish(nullptr), end_of_storage(nullptr) {}vector(int n, const T& val = T()) : start(new T[n]), finish(start + n), end_of_storage(start + n) {//放入数据for (int i = 0; i < n; ++i) {start[i] = val;}}//写范围构造函数template<class InputIterator>vector(InputIterator first, InputIterator last) {//利用范围进行构造while (first != last) {push_back(*first++);//直接进行复用接口}}//接下来写拷贝构造, 赋值运算符重载,移动构造,全部进行复用接口void swap(vector<T>& vec) {::swap(start, vec.start);::swap(finish, vec.finish);::swap(end_of_storage, vec.end_of_storage);}vector(const vector<T>& vec) : start(nullptr), finish(nullptr), end_of_storage(nullptr) {vector<T> tmp(vec.begin(), vec.end());swap(tmp);//复用范围构造代码}vector<T>& operator=(vector<T> vec) {swap(vec);//复用拷贝构造代码return *this;}//移动构造, 窃取资源,窃取将亡对象的底层堆区资源//反正你都要死亡了不如用来给我构造vector(vector<T>&& vec) : start(nullptr), finish(nullptr), end_of_storage(nullptr) {swap(vec);}iterator begin() {return start;}const_iterator begin() const {return start;}iterator end() {return finish;}const_iterator end() const {return finish;}void resize(size_t n, const T& val = T()) {if (n <= size()) return;	//啥事不用做//至此说明了超出的部分需要设置为valif (n > capacity()) reserve(n);//先扩容//然后赋值while (finish != start + n) {*finish++ = val;}}void reserve(int n) {//预先开空间,三部曲目if (n <= capacity()) return;//至此说明需要重新开空间T* pTemp = new T[n];size_t sz = size();//保存之前容器中的元素大小//转移数据for (int i = 0; i < sz; ++i) {pTemp[i] = start[i];}delete [] start;//删除掉原有的空间start = pTemp;finish = pTemp + sz;end_of_storage = start + n;}void push_back(const T& val) {if (finish == end_of_storage) {reserve(capacity() > 0 ? capacity() << 1 : 4);}//有了空间,然后就是进行数据插入*finish++ = val;//放入数据}bool empty() {return start == nullptr;}size_t size() {return finish - start;}size_t capacity() {return end_of_storage - start;}//网pos位置插入一个元素,插入一定谨防的是插入扩容的原有迭代器失效问题iterator insert(iterator pos, const T& val) {assert(pos >= start && pos <= finish);//断言位置合法if (finish == end_of_storage) {size_t step = pos - start;//扩容首先reserve(capacity() > 0 ? capacity() << 1 : 4);//扩容之后原有的pos迭代器会失效跟新pos = start + step;}//拿到finish迭代器同时finish迭代器后移动iterator it = finish++;//腾出空间while (it != pos) {*it = *(it - 1);--it;}*pos = val;//放入插入数据return pos;//返回插入位置元素}//删除一定注意的是删除的位置其实还是pos 因为返回下一个元素其实是覆盖到pos位置了iterator erase(iterator pos) {//覆盖删除整个元素assert(pos >= start && pos < finish);iterator it = pos + 1;while (it <= finish) {*(it - 1) = *it;//覆盖删除++it;}--finish;//尾部迭代器前移动return pos;}~vector() {if (start) {delete[] start;}start = finish = end_of_storage = nullptr;}private:T* start;T* finish;T* end_of_storage;};template<class InputIterator, class Function>void for_each(InputIterator first, InputIterator last, Function f) {while (first != last) {f(*first);++first;}}template<class T>struct Print {void operator()(T& val) const {cout << val << " ";}};
}
template<class T>
void PrintVector(tyj::vector<T>& vec) {tyj::for_each(vec.begin(), vec.end(), tyj::Print<T>());cout << endl;
}

测试代码

void TestVector3()
{int a[] = { 1, 2, 3, 4 };tyj::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));// 使用find查找3所在位置的iteratorauto pos = find(v.begin(), v.end(), 3);//pos迭代器可以失效,  插入操作迭代器也会失效// 在pos位置之前插入30v.insert(pos, 30);PrintVector(v);// 删除pos位置的数据pos = find(v.begin(), v.end(), 3);v.erase(pos);PrintVector(v);
}void TestVector1()
{// constructors used in the same order as described above:tyj::vector<int> first; // empty vector of tyj::vector<int> second(4, 100); // four ints with value tyj::vector<int> third(second.begin(), second.end()); // iterating through tyj::vector<int> fourth(third); // a copy of third// the iterator constructor can also be used to construct from arrays:int myints[] = { 16, 2, 77, 29 };tyj::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));std::cout << "The contents of fifth are:";for (tyj::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)std::cout << *it << " ";std::cout << endl;// 测试T是string时,拷贝问题tyj::vector<string> strV;strV.push_back("1111");strV.push_back("2222");strV.push_back("3333");strV.push_back("4444");}void TestVector2()
{// 使用push_back插入4个数据tyj::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);PrintVector(v);// 使用迭代器进行修改auto it = v.begin();while (it != v.end()){*it *= 2;++it;}PrintVector(v);// 这里可以看出C++11支持iterator及接口,就支持范围forfor (auto e : v)cout << e << " ";
}// iterator失效问题
void TestVector4()
{int a[] = { 1, 2, 3, 4 };tyj::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));// 删除pos位置的数据,导致pos迭代器失效auto pos = find(v.begin(), v.end(), 3);v.erase(pos);cout << *pos << endl; // 此处会导致非法访问// 在pos位置插入数据,导致pos迭代器失效。// insert会导致迭代器失效,是因为insert可// 能会导致增容,增容后pos还指向原来的空间,而原来的空间已经释放了。pos = find(v.begin(), v.end(), 3);v.insert(pos, 30);cout << *pos << endl; // 此处会导致非法访问// 实现删除v中的所有偶数// 下面的程序会崩溃掉,如果是偶数,erase导致it失效
// 对失效的迭代器进行++it,会导致程序崩溃auto it = v.begin();//while (it != v.end())//{//	if (*it % 2 == 0)//		v.erase(it);//	++it;//每一次erase之后进行跳跃//}// 以上程序要改成下面这样,erase会返回删除位置的下一个位置it = v.begin();PrintVector(v);while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}
}int main() {//tyj::vector<int> vec1;//for (int i = 0; i < 5; ++i) {//	vec1.push_back(i);//}//PrintVector<int>(vec1);//tyj::vector<int> vec2;//vec2.resize(5, 1);//PrintVector<int>(vec2);//int nums[5] = { 1, 2, 3, 4, 5 };//tyj::vector<int> vec3(nums, nums + sizeof(nums) / sizeof(int));//PrintVector<int>(vec3);//tyj::vector<int> vec4(vec3);//PrintVector<int>(vec4);//TestVector3();//TestVector2();//TestVector4();TestVector1();return 0;
}

五. 整合小结一下,以及特别谈一谈如何写一个STL容器和迭代器设计思想(迭代器是什么),迭代器失效的问题.

  • 如何实现一个STL书写的方法论

  • 首先分析如果要写一个STL容器应该如何下手的问题,找到一个官方文档分析组件 + 接口
  • 推荐官方文档网址:   www.cplusplus.com   
  • 写一个STL 需要将迭代器设计和整体的设计分开来,先实现迭代器的设计 + 实现最简单的插入接口 (完成框架),测试插入接口,一来可以获得一定成就,而来可以知道自己基本框架是否搭建正确
  • 阅读文档分析重点接口函数,可以买一本STL源码刨析,结合侯捷老师的讲述去设计接口,   将有用的接口一一实现.   (在实现的过程中不断测试以及发现细节坑点)
  • 总结实现细节中出现的坑点   +  快速复现重写整个框架  (记忆熟练)
  • 其实谈迭代器的设计在此处不算很合适,因为T* 就是一个原生指针,而且还是连续的线性存储空间,原生指针作为迭代器,本身迭代器就支持  ++  --  *  这些操作,加之元素本身就是连续存储的,  所以此处没有对迭代器的设计画太多功夫。
  • 迭代器,算是一个智能指针类的感觉,但是也不完全是,可以帮助我们管理访问容器中的元素,支持 ++  -- *  这些操作来访问复杂存储结构中的  元素。
  • 迭代器的设计是为了统一,是为了做粘合剂,做通用各式各样容器和算法之间的粘合剂,  有了迭代器,我们才能做各式各样容器的统一泛型算法操作,才能统一各种格式各样的容器元素的遍历方式,提供统一遍历接口.   是STL中特别重要的组件

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5p2wMzEy,size_20,color_FFFFFF,t_70,g_se,x_16

上述这些算法,没有迭代器根本不可能这样写

  • 迭代器失效,说白了其实本质是内存问题,扩容后,原来的迭代器全部不可以用了,因为原来的迭代器指向原来的那片空间,可是 扩容后原来那片空间都释放掉了,你如何敢访问,所以每一次关于迭代器的操作我们需要接收返回值就是这个道理,跟新旧的迭代器,避免使用失效迭代器,     it = e.erase(it)            不能是    e.erase(it++); ; 因为删除之后你不清楚,it   的情况如何,但是返回迭代器是指向下一个元素的有效迭代器,所以需要接收返回值.              删除it 之后 it 本质是一个失效迭代器了,如何赶直接  ++  因为他的本质在接收返回值之前还是哪个即将别删除的迭代器
  • 所以 删除,插入扩容,都可能导致迭代器失效,插入失效是因为扩容,删除失效是因为它已经别干掉了,很可能是delete  或者其他操作

这篇关于分块刨析从函数原型到分块实现C++STL(vector)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/729828

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名