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,安卓与i... 你有没有发现,现在身边的朋友几乎人手一台平板电脑呢?无论是追剧、办公还是游戏,平板电脑都成了我们生活...
安卓的定位系统叫什么,GPS导... 你有没有想过,你的手机是怎么知道你在哪儿的呢?是不是觉得这事儿很神奇?其实,这背后有一个强大的技术支...
老式电视安卓系统升级,解锁智能... 你有没有发现,家里的老式电视突然变得聪明起来啦?没错,就是那个陪伴我们多年的老伙伴,它竟然悄悄地升级...
长安车载系统升级安卓 你有没有发现,最近你的长安车好像变得聪明多了?没错,就是那个车载系统,它悄悄地进行了安卓升级,简直就...
安卓系统损坏标志图,故障原因与... 手机突然间闹起了脾气,屏幕上那个安卓系统损坏的标志图,简直就像是个不速之客,突然闯进了你的生活。别急...
安卓系统自带投屏,轻松实现多屏... 你是不是也和我一样,有时候想把自己的手机屏幕上的内容分享给朋友或者家人看,但又觉得用数据线连接太麻烦...
mac可以下安卓系统么 亲爱的果粉们,你是否曾有过这样的疑问:Mac可以下安卓系统吗?这个问题,不仅让你我好奇,也让不少科技...
diy主机安卓系统推荐 亲爱的DIY爱好者们,你是否曾梦想过拥有一台完全由自己组装的安卓主机?想象一台运行流畅、功能强大的安...
安卓13系统可以安装吗 你有没有听说安卓13系统已经发布了?是不是迫不及待想要升级你的手机,体验一下新系统的魅力呢?不过,在...
手机壳平价推荐安卓系统,时尚与... 手机壳可是咱们手机的最佳守护者呢!想象你的宝贝手机在日常生活中难免会遭遇各种“小意外”,有了手机壳,...
麦芒是安卓系统吗,深度解析安卓... 你有没有想过,手机里的那个麦芒,它是不是安卓系统呢?这个问题,估计不少手机控都好奇过吧!今天,就让我...
苹果x系统感觉像安卓,安卓风潮... 你有没有发现,最近苹果的X系统好像有点儿像安卓呢?是不是觉得苹果的“高贵”形象突然变得有点儿接地气了...
小米的安卓系统设置在哪,轻松生... 你有没有发现,小米手机的操作界面简洁又美观,功能强大到让人爱不释手?但是,有时候你可能会觉得,这个设...
安卓系统荣耀排第一,引领智能手... 你知道吗?在智能手机的世界里,有一个系统可是风头无两,那就是安卓系统!而在这众多安卓手机品牌中,有一...
充电宝带安卓系统,便携式智能电... 你有没有想过,你的充电宝也能拥有自己的操作系统呢?没错,就是安卓系统!听起来是不是很酷?想象你的充电...
安卓类原生系统手机推荐,精选原... 你有没有想过,拥有一部安卓类原生系统手机,就像是拥有了掌控自己世界的魔法棒?没错,原生系统带来的流畅...
努比亚安卓13系统下载,下载与... 你有没有听说?努比亚手机最近可是大动作连连呢!他们推出了全新的安卓13系统,而且现在就可以下载啦!是...