C++学习记录——십삼 List
创始人
2024-06-01 14:44:40
0

文章目录

  • 1、认识List
  • 2、list模拟实现


1、认识List

List实际上是一个双向带头循环列表。

想要遍历List就使用迭代器,方括号只是特定的一种,而迭代器则是通用的。

	list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;

列表库中提供了一个sort,不用算法库中的sort,是因为算法库中的sort用了快排,需要三数取中,这对于链表来讲很不高效。虽然模板语法上可传任意类型参数,但内部使用迭代器对迭代器有要求,库里接口参数的名字会暗示要传随机迭代器。

迭代器分为三种,单向,双向,随机。单向迭代器例子就是单链表,只能++;链表就是双向迭代器,可++,可–;vector,string的迭代器就是随机迭代器,++ – 以及加减都可用。

要求传单向也可以传双向,随机,要求传双向也可以传随机。

不过列表用sort,显而易见,性能不够好。

2、list模拟实现

写完这篇后我修改了一下,完整代码在这里:

https://gitee.com/kongqizyd/start-some-c-codes-for-learning.c/tree/master/List

先开个头

	templatestruct list_node{list_node* next;list_node* prev;T data;};templateclass list{typedef list_node node;public:list(){head = new node;head->prev = head;head->next = head;}private:node* _head;};

添加插入函数

	struct list_node{list_node* next;list_node* prev;T data;list_node(const T& x):next(nullptr), prev(nullptr), data(x){}};
		void push_back(const T& x){node* tail = head->prev;node* newnode = new node(x);tail->next = newnode;newnode->prev = tail;newnode->next = head;head->prev = newnode;}

如果是单纯的链表结构,那么用一个指针指向一个节点,++就能到下一个节点,但是现在创建的链表不是这样,它的类型是list_node < int >*类型的,解引用后就是list_node,不一定能++正确,它不像链表一样是连续的物理空间。再造一个结构体,里面做些重载函数。

现有一个类list和一个结构体list_node, 在list之前再加一个结构体。

	templatestruct _list_iterator{typedef list_node node;typedef _list_iterator self;node* _node;_list_iterator(node* n):_node(n){}T& operator*(){return _node->data;}self& operator++(){_node = _node->next;return *this;}bool operator!=(const self& s){return _node != s._node;}};

然后在list类里写上测试代码

	void Test_list1(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}

用struct写是为了公开代码,让代码不受限制。测试代码中的迭代器,begin赋值给it,是浅拷贝,因为我们没写拷贝构造,但是也过了;是因为这里没写析构函数,而且节点不需要释放,因为节点不是迭代器结构体的,而是其他结构体的,所以它没有资格释放。除此之外,前后置+±-以及等于和不等于函数

		self& operator++(){_node = _node->next;return *this;}self operator++(int){self tmp(*this);_node = _node->next;return tmp;}self& operator--(){_node = _node->prev;return *this;}self operator--(int){self tmp(*this);_node = _node->prev;return tmp;}bool operator==(const self& s){return _node != s._node;}bool operator!=(const self& s){return _node != s._node;}

以及begin和end加上const版本和打印函数

		iterator begin(){return iterator(head->next);}iterator begin() const{return iterator(head->next);} iterator end(){return iterator(head);}iterator end() const{return iterator(head);}void print_list(const list& lt){list::iterator it = lt.begin();while (it != lt.end()){(*it) *= 2;cout << *it << " ";++it;}cout << endl;}

但是用const的begin和end构造出来的迭代器里面可以修改数值,这是因为他们构造出来普通迭代器,内容依然可以修改,const修饰的只是指针而已,不是内容。我们要返回const迭代器。

之前已经写过typedef _list_iterator< T > iterator,那么可不可以这样写
typedef const iterator const_iterator。

这就相当于T和T const,也就是这样把迭代器本身变成不可修改了。const迭代器应当可以++,我们要的是cosnt T*。

我们可以这样写,再创建一个结构体,然后把名字中加上const,和原有结构体区分开来。然后改一下这个函数

		const T& operator*(){return _node->data;}

list类里

	templateclass list{typedef list_node node;public:typedef _list_iterator iterator;typedef _list_const_iterator const_iterator;const_iterator end() const{return const_iterator(head);}const_iterator begin() const{return const_iterator(head->next);} 

打印函数里就是这样

list::const_iterator it = lt.begin();

然后把之前那个const结构体去掉,归到原先的结构体里,引入新的模板

	templatestruct _list_iterator{typedef list_node node;typedef _list_iterator self;node* _node;_list_iterator(node* n):_node(n){}Ref operator*(){return _node->data;}
	templateclass list{typedef list_node node;public:typedef _list_iterator iterator;typedef _list_iterator const_iterator;//typedef _list_const_iterator const_iterator;

如果传的是普通的,那就是T和T&。如果是const对象,那就是T和const T&,在_list_iterator结构体那里const T&就是Ref.

继续看迭代器的使用

	struct AA{int _a1;int _a2;AA(int a1, int a2):_a1(a1),_a2(a2){}};void test_list2(){list lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";}cout << endl;}

程序会报错,因为it是AA的数据,需要重载<<。但还有别的办法

		list::iterator it = lt.begin();while (it != lt.end()){cout << it->_a1<< ":" << it->_a2 << " ";++it;}cout << endl;

本质是指针的迭代器,这样写貌似看起来更合理,那么就得重载->这个符号。在list_iterator写上这个函数

		T* operator->(){return &_node->data;}

其实本应当是it->->_a1。it一次解引用得到AA*,再次解引用得到AA,不过编译器就会识别为2个。原本的写法是这样:cout << it.operator->()->_a1 << “:” << it.operator->()->_a2 << " ";

如果这里是const,那么又要增加一个模板参数。

完善列表,写插入等函数。

		void push_back(const T& x){/*node* tail = head->prev;node* newnode = new node(x);tail->next = newnode;newnode->prev = tail;newnode->next = head;head->prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){node* cur = pos.node;node* _prev = cur->prev;node* newnode = new node(x);prev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;}void erase(iterator pos){assert(pos != end());node* prev = pos.node->prev;node* next = pos.node->next;prev->next = next;next->prev = prev;delete pos.node;}

写上clear函数以及要让erase函数传回来现在的位置还有析构函数。

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}
		iterator erase(iterator pos){assert(pos != end());node* prev = pos.node->prev;node* next = pos.node->next;prev->next = next;next->prev = prev;delete pos.node;return iterator(next);}
		~list(){clear();delete head;head = nullptr;}

迭代器区间函数,顺便改一下初始化。

		void empty_init(){head = new node;head->next = head;head->prev = head;}list(){empty_init();}templatelist(Iterator first, Iterator last){empty_init();while (firse != last){push_back(*first);++first;}}

拷贝构造,两种方式。

		void swap(list& tmp){std::swap(head, tmp.head);}list(const list& lt){/*empty_init();for (auto e : lt){push_back(e);}*/list tmp(lt.begin(), lt.end());swap(tmp)}

重载=

		list& operator=(list lt){swap(lt);return *this;}

结束。

相关内容

热门资讯

安卓系统用的华为应用,探索智能... 你知道吗?在安卓系统里,华为的应用可是个宝库呢!它们不仅功能强大,而且使用起来超级方便。今天,就让我...
安卓变ios系统魅蓝 你知道吗?最近有个朋友突然告诉我,他要把自己的安卓手机换成iOS系统,而且还是魅蓝品牌的!这可真是让...
幻书启世录安卓系统,安卓世界中... 亲爱的读者们,你是否曾在某个夜晚,被一本神奇的书所吸引,仿佛它拥有着穿越时空的力量?今天,我要带你走...
电脑安装安卓系统进不去,安卓系... 电脑安装安卓系统后竟然进不去,这可真是让人头疼的问题啊!你是不是也遇到了这种情况,心里直呼“怎么办怎...
用键盘切换控制安卓系统,畅享安... 你有没有想过,用键盘来控制你的安卓手机?是的,你没听错,就是那个我们每天敲敲打打的小玩意儿——键盘。...
小米安卓镜像系统在哪,小米安卓... 你有没有想过,你的小米手机里有一个隐藏的宝藏——安卓镜像系统?没错,就是那个可以让你的手机瞬间变身成...
安卓手机下载排班系统,高效排班... 你有没有想过,每天忙碌的工作中,有没有什么好帮手能帮你轻松管理时间呢?今天,就让我来给你介绍一个超级...
桌面组件如何弄安卓系统,桌面组... 亲爱的桌面爱好者们,你是否曾梦想过将安卓系统搬到你的电脑桌面上?想象那些流畅的动画、丰富的应用,还有...
安卓13系统介绍视频,新功能与... 亲爱的读者们,你是否对安卓13系统充满好奇?想要一探究竟,却又苦于没有足够的时间去研究?别担心,今天...
车机安卓7.1系统,功能升级与... 你有没有发现,现在的车机系统越来越智能了?尤其是那些搭载了安卓7.1系统的车机,简直就像是个贴心的智...
安卓系统下如何读pdf,And... 你有没有遇到过这种情况:手机里存了一大堆PDF文件,可是怎么也找不到一个能顺畅阅读的工具?别急,今天...
安卓系统全国通用的吗,畅享智能... 你有没有想过,为什么你的手机里装的是安卓系统呢?安卓系统,这个名字听起来是不是有点神秘?今天,就让我...
假苹果手机8安卓系统,颠覆传统... 你有没有想过,如果苹果手机突然变成了安卓系统,会是怎样的景象呢?想象那熟悉的苹果外观,却运行着安卓的...
安卓12.0系统vivo有吗,... 你有没有听说最近安卓系统又升级啦?没错,就是那个让手机焕然一新的安卓12.0系统!那么,咱们国内的手...
核心芯片和安卓系统,探索核心芯... 你知道吗?在科技的世界里,有一对“黄金搭档”正悄悄改变着我们的生活。他们就是——核心芯片和安卓系统。...
如何调安卓系统屏幕颜色,安卓系... 亲爱的手机控们,你是否曾觉得安卓系统的屏幕颜色不够个性,或者是因为长时间盯着屏幕而感到眼睛疲劳?别担...
旧台式电脑安装安卓系统,轻松安... 你那台旧台式电脑是不是已经服役多年,性能逐渐力不从心,却又不忍心让它退役呢?别急,今天就来教你怎么给...
美国要求关闭安卓系统,科技霸权... 美国要求关闭安卓系统:一场技术革新还是政治博弈?在数字化时代,智能手机已经成为我们生活中不可或缺的一...
安卓系统日记本 你有没有发现,手机里的安卓系统日记本,简直就是记录生活点滴的宝藏库呢?想象每天忙碌的生活中,有没有那...
安卓手机广告最少的系统,探索安... 你有没有发现,用安卓手机的时候,广告总是无处不在,让人烦得要命?不过别急,今天我要给你揭秘一个秘密—...