当前位置: 首页> 游戏> 单机 > 搜索李晓峰_品牌建设内容_友情链接交换网站_宁波seo推广优化公司

搜索李晓峰_品牌建设内容_友情链接交换网站_宁波seo推广优化公司

时间:2025/7/11 20:37:38来源:https://blog.csdn.net/Farewell_me/article/details/142389272 浏览次数:0次
搜索李晓峰_品牌建设内容_友情链接交换网站_宁波seo推广优化公司

文章目录

  • 前言
  • 一、list
  • 二、list类的初始化和尾插
  • 三、list的迭代器的基本实现
  • 四、list的完整实现
  • 五、测试
  • 六、整个list类
  • 总结


前言

C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍


一、list

list本质上是一个双向带头循环链表。
实现list类,需要节点类(clase list_node)、迭代器(class __list_iterator);
节点类(clase list_node): 定义每个节点的结构;
迭代器(class __list_iterator): 使用节点的指针封装出一个类,可以使用运算符重载的形式更好的访问链表;

二、list类的初始化和尾插

namespace hhb
{// 节点template <class T>struct list_node{list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _val(val){}list_node<T>* _next;list_node<T>* _prev;T _val;};// 链表template<class T> class list{typedef list_node<T> Node;public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){Node* newNode = new Node(x);Node* tail = _head->_prev;newNode->_next = _head;newNode->_prev = tail;tail->_next = newNode;_head->_prev = newNode;}private:Node* _head;};
}

在这里插入图片描述

三、list的迭代器的基本实现

  • 使用链表节点的指针封装出一个类,是list链表的访问可以向vector一样使用++等操作访问
  • vector和list的使用,虽然在形式上一样,但是他们的底层是不一样的
  • (*)vector迭代器是对指针的解引用
  • (*)list迭代器是调用operator(解引用操作符)函数重载,本质是不一样的

对于const迭代器,是operator(*)和 operator(->)的运算符重载函数的返回值不一样,因此需要增加两个模板参数

  • 即: (T& 和 T*)
// 迭代器
template <class T, class Ref, class Ptr>
struct __list_iterator
{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;
public:__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}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& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}Node* _node;
};
  • operator->运算符重载编译器会进行优化, 如下:
struct A
{
public:A(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}int _a1;int _a2;
};
void test_list02()
{hhb::list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));lt.push_back(A(5, 5));hhb::list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;cout << it->_a1 << " " << it->_a2 << " " << endl;// 此处编译器进行了优化, it->返回的是T* 也就是 A*, 如果要访问A的成员// 按道理来讲,应该是 (it->)->_a1 / (it->)->_a2 来进行访问++it;}cout << endl;}

在这里插入图片描述

四、list的完整实现

  • list需要有size()的接口,所以需要对链表节点个数进行计数,增加一个成员变量_size.
  • 实现insert()和erase()接口后,push_back()和push_front()、pop_back()和pop_front()接口都可以复用接口。
  • clear()只清除(不包含哨兵位的头节点)数据,不销毁链表
  • 析构函数调用clear()后,释放_head节点(哨兵位的头节点)
  • 拷贝构造函数在拷贝之前,一定要先自己初始化(创建哨兵位的头节点)
  • 赋值(=)运算符重载使用现代写法,拷贝构造加交换函数加自动调用析构函数。
	// 链表template<class T> class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void emptyInit(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){emptyInit();}list(const list<T>& lt){emptyInit();for (auto e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T> operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;_size = 0;}void push_back(const T& x){//Node* newNode = new Node(x);//Node* tail = _head->_prev;//newNode->_next = _head;//newNode->_prev = tail;//tail->_next = newNode;//_head->_prev = newNode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pos_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;newNode->_next = cur;newNode->_prev = prev;cur->_prev = newNode;prev->_next = newNode;++_size;return newNode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;--_size;return next;}//size_t size()//{//	int sz = 0;//	iterator it = begin();//	while (it != end())//	{//		sz++;//		++it;//	}//	//	return sz;//}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private:Node* _head;size_t _size;};
}

五、测试

  • 测试push_back, pop_back可以顺便测试insert, erase函数, 所以不单独测试insert和erase函数
void test_list03()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pos_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);lt.push_back(50);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;}

在这里插入图片描述

  • 测试拷贝构造和赋值运算符重载
void test_list04()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;hhb::list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;hhb::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}

在这里插入图片描述

六、整个list类

// list.h
#pragma once#include <assert.h>
namespace hhb
{// 节点template <class T>struct list_node{list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _val(val){}list_node<T>* _next;list_node<T>* _prev;T _val;};// 迭代器template <class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;public:__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}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& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}Node* _node;};// 链表template<class T> class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void emptyInit(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){emptyInit();}list(const list<T>& lt){emptyInit();for (auto e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T> operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;_size = 0;}void push_back(const T& x){//Node* newNode = new Node(x);//Node* tail = _head->_prev;//newNode->_next = _head;//newNode->_prev = tail;//tail->_next = newNode;//_head->_prev = newNode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pos_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;newNode->_next = cur;newNode->_prev = prev;cur->_prev = newNode;prev->_next = newNode;++_size;return newNode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;--_size;return next;}//size_t size()//{//	int sz = 0;//	iterator it = begin();//	while (it != end())//	{//		sz++;//		++it;//	}//	//	return sz;//}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private:Node* _head;size_t _size;};
}
  • 整个测试
#define  _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <list>
using namespace std;
#include "list.h"void print1(const hhb::list<int>& lt)
{hhb::list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}void test_list01()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);hhb::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;print1(lt);
}struct A
{
public:A(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}int _a1;int _a2;
};void test_list02()
{hhb::list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));lt.push_back(A(5, 5));hhb::list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;cout << it->_a1 << " " << it->_a2 << " " << endl;// 此处编译器进行了优化, it->返回的是T* 也就是 A*, 如果要访问A的成员// 按道理来讲,应该是 (it->)->_a1 / (it->)->_a2 来进行访问++it;}cout << endl;}void test_list03()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pos_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);lt.push_back(50);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;}void test_list04()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;hhb::list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;hhb::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}int main()
{//test_list01();test_list02();//test_list03();//test_list04();return 0;
}

总结

C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍

关键字:搜索李晓峰_品牌建设内容_友情链接交换网站_宁波seo推广优化公司

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: