C++学习之list的实现

这篇具有很好参考价值的文章主要介绍了C++学习之list的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在了解学习list实现之前我们首先了解一下关于迭代器的分类:

按功能分类:

正向迭代器    反向迭代器

const正向迭代器  const反向迭代器

按性质分类:

单向迭代器      只能++    例如单链表

 双向迭代器     可++,也可--     例如双链表 ,map和set

 随机迭代器     可加加,可减减,可+,可减  如顺序表(vector string),deque(双端队列)

这些都是由容器的底层实现。

C++学习之list的实现,学习

可以看到库中提供的list模板是带头双向链表,故此我们实现它就大部分操作都是在数据结构中实现双链表时是一样。

目录

1.成员变量

节点类型的定义:

迭代器

重载前置++/--

重载后置++/--

重载*与->

重载!=与==

const迭代器

迭代器的优化:

反向迭代器 

const反向迭代器 

成员函数

构造函数

析构函数

拷贝构造函数

容量

size

修饰符 

insert()

erase ()

push_front()

pop_front()

push_back()

pop_back()

clear()


1.成员变量

template<class T>class mylist
	{
        typedef list_node<T>  Node;
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T,const T&,const T*> const_iterator;
private:
		Node* _head;
		size_t _size;
......
}

因为实现的是链表,故此我们的成员变量是链表头节点与链表的大小,这里我们还需要给出

节点类型的定义:

typedef list_node<T>  Node;
template<class T>struct list_node
	{
		//我们给一个缺省值为T的匿名对象
		list_node(const T& x = T())
			:data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
		T data;
		list_node<T>* _next;
		list_node<T>* _prev;
	};

迭代器

因为我们实现的是链表,那么迭代器的操作也就是链表节点的操作,节点并非一般的数据类型,

故此我们这里需要封装迭代器,迭代器本质是节点的地址:

//迭代器
	//认真思考的话,迭代器模拟的是一个双链表节点的运动,故我们封装迭代器里面一定是节点,这里放入节点的地址
	//并且重载对应的运算符,封装之后,我们在定义为iterator
	template<class T>struct _list_iterator
	{
		//利用节点的指针实现迭代器
		typedef list_node<T>  Node;
		typedef _list_iterator<T> self;
		Node* _node;
        _list_iterator(Node* node)
			:_node(node)
		{}

	};

封装之后,我们还需要重载对于迭代器的运算符,这些重载都是在迭代器中的,我只是为了吧方法一个个体现出来,分开了。

重载前置++/--

       //重载加加
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

重载后置++/--

       self& operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--(int)
		{
			self tmp(*this);
			_node = _node->prev;
			return tmp;
		}
		

重载*与->

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

重载!=与==

bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		bool operator==(const self& s)
		{
			return _node == s._node;
		}

const迭代器

const迭代器对应const对象,指的是内容不能被修改,而非指针(迭代器)本身,因此我们不能直接const iterator去认为是const迭代器,这样反而不能对迭代器进行++等操作,而需要我们去重新定义
 定义const迭代器,即内容是无法被修改,由于我们访问内容是通过解引用的方法故我们需要修改访问的的这两个操作符其引用返回为const,即内容无法被修改了。

template<class T>struct _list_const_iterator
	{
		typedef list_node<T>  Node;
		typedef _list_const_iterator<T> self;
		Node* _node;
		_list_const_iterator(Node* node)
			:_node(node)
		{}
		//迭代器的运算符重载
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		self& operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--(int)
		{
			self tmp(*this);
			_node = _node->prev;
			return tmp;
		}
		const T* operator->()
		{
			return &_node->data;
		}
		const T& operator*()
		{
			return &_node->data;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};

由于const迭代器与普通的迭代器区别也就在于访问的内容无法被修改,也就是修改*与->这两个访问内容的操作符,重新实现较为麻烦,库中实现是增加了两个模板参数Ref,Ptr,利用我们传的参数不一样,从而决定用的是哪一个迭代器。

迭代器的优化:

多出两个模板参数之后,我们的*与->返回类型就是到时候传入时候的类型,故这里我们直接用Ref与Ptr代替即可。

template<class T,class Ref,class Ptr>struct _list_iterator
	{
		//利用节点的指针实现迭代器
		typedef list_node<T>  Node;
		typedef _list_iterator<T,Ref,Ptr> self;
		Node* _node;
        _list_iterator(Node* node)
			:_node(node)
		{}
}
        Ptr operator->()
		{
			return _node->data;
		}
		Ref operator*()
		{
			return &_node->data;
		}

 在list中,对于模板迭代器我们传参不一样,决定了是const还是普通

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T,const T&,const T*> const_iterator;
        iterator begin()
		{
			//return iterator(_head->data);
			return _head->_next;
		}
		iterator end()
		{
			return _head;//哨兵位就是链表的结束标志
		}
		const_iterator begin()const
		{
			return _head->_next;
		}
		const_iterator end()const
		{
			return _head;
		}

反向迭代器 

反向迭代器与正向迭代器的区别就在于遍历的反向不一样了,两者的本质是非常相似的,那么我们就可以利用正向得带起适配出一个反向迭代器。我们直接将正向的封装成一个反向迭代器:

//利用正向迭代器去适配一个反向迭代器
template <class iterator,class Ref ,class Ptr>class Reverse_iotearator
{
public:

	Reverse_iotearator(iterator it)
		:_it(it)
	{}
	Reverse_iotearator<iterator, Ref, Ptr>operator++()
	{
		--_it;
		return *this;
	}
	Ref operator*()
	{
		return *_it;
	}
	Ptr operator->()
	{
		return _it.operator->();//这里需要显式调用不能直接->
	}
	Reverse_iotearator<iterator,Ref ,Ptr>operator()
	{
		++_it;
		return *this;
	}
	bool operator!=(const Reverse_iotearator<iterator, Ref, Ptr>& it)
	{
		return _it != it;
	}
private:
	iterator _it;
};

 实现一个rever_iterator的类,其模板参数分别用正向迭代器,数据的类型,数据地址类型做参数也实现了对于反向迭代器数据的访问。

之后就可以包含该类,封装出反向迭代器:

//反向迭代器
		typedef Reverse_iterator<iterator, T&,  T*> reverse_iterator;
		
		reverse_iterator rbegin()
		{
			//return _head->_next;
			return reverse_iterator(--end());//直接调用构造函数 
		const_reverse_iterator rend()const
		{
			//return _head;
			return reverse_iterator(end());
		}

 同理实现了反向迭代器我们直接可以实现const的反向迭代器

const反向迭代器 

typedef Reverse_iterator<const_iterator, const T&, const T*>const_reverse_iterator;

const_reverse_iterator rend()const
		{
			//return _head;
			return reverse_iterator(end());
		}
		const_reverse_iterator rbegin()const
		{
			//return _head->_next;
			return reverse_iterator(--end());
		}

成员函数

构造函数

       //通过调用一个初始化链表的函数来实现构造函数
       mylist()
		{
			empty_init();
		}

析构函数

      //通过调用clear函数释放链表的节点,在释放哨兵位,即为析构
 ~mylist()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

拷贝构造函数

//拷贝构造,将节点尾插入新的对象
		mylist(mylist<T>& p)
		{
			empty_init(p);
			for (auto it : p)
			{
				push_back(it);
			}
		}

容量

size

size_t size()
		{
			return _size;
		}

修饰符 

insert()

在基于实现insert,我们的其他对list的操作都可以调用insert,不需要都去对链表节点一个个操作,

其次我们设计insert的返回值及参数位置都是迭代器,直接用。

iterator insert(iterator pos, const T x)//插入也会使迭代器失效,原位置节点找不到了
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;
			//链接节点
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_size++;
			return iterator(newnode);
		}

erase ()

//删除   这里删除cur节点释放掉,会导致迭代器失效,因此要返回下一节点的迭代器
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			_size--;
			return iterator(next);
		}

push_front()

void push_front()
		{
			insert(begin());
		}

pop_front()

//头删
		void pop_front()
		{
			erase(begin());
		}

push_back()

//尾插
		void push_back(const T& x)
		{
			//Node* tail = _head->preav;
			//Node* newnode = new Node(x);
			连接节点
			//tail->_next = newnode;
			//newnode->_next = _head;
			//newnode->prev = tail;
			//tail->_prev = newnode;
			//tail = newnode;
			//return (tail);
			insert(end(), x);
		}

pop_back()

//尾删
		void pop_back()
		{
			erase(end());
		}

clear()

//清数据
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
         }

至此我们对list的简单实现就完成了。文章来源地址https://www.toymoban.com/news/detail-707664.html

到了这里,关于C++学习之list的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • c++ 学习之 类的权限访问修改学习

    当分析这段代码时,涉及的主要概念包括: 成员函数和成员变量: 在类 person 中,有三个成员函数:set_name、get_name 和 fun,以及两个成员变量:name 和 age。 成员函数用于操作和访问成员变量,可以在类内部定义其实现。 成员变量存储类的状态和数据。 访问权限: set_name、

    2024年02月10日
    浏览(32)
  • C++学习-List学习

    2024年01月21日
    浏览(31)
  • c++学习之string实现

    字符串 - C++引用 (cplusplus.com)这里给出标准官方的string实现,可以看到设计还是较为复杂的,有成员函数,迭代器,修饰符,容量,元素访问,字符串操作等,将字符尽可能的需求都设计出来,我们这里实现string中比较常用且重要的。 成员变量 目录 1.迭代器实现 2.成员函数

    2024年02月11日
    浏览(33)
  • C++学习:list

    1.list的定义和结构 list的使用频率不高,在做题时几乎遇不到需要使用list的情景。list是一种双向链表容器,它是标准模板库(STL)提供的一种序列容器。list容器以节点(node的形式存储元素,并使用指针将这些节点链接在一起,形成一个链表结构。list容器结构如下: list容器模板接

    2024年02月20日
    浏览(29)
  • C++ STL学习之【string的模拟实现】

    ✨个人主页: Yohifo 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 The key is to keep company only with people who uplift you, whose presence calls forth your best. 关键是只与那些提升你的人在一起,他们的存在唤起了你最好的一面。 string 本质上就是一个专注于存储字符的顺序表,使用起来

    2023年04月09日
    浏览(60)
  • C++ STL学习之【vector的模拟实现】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 The power of imagination makes us infinite. 想象力的力量使我们无限。 vector 是 STL 中的容器之一,其使用方法类似于数据结构中的 顺序表 ,得益于范型编程和 C++ 特性的加持, vector 更强大、更全能;在模拟实现

    2023年04月08日
    浏览(64)
  • 【C++ 学习 ⑬】- 详解 list 容器

    目录 一、list 容器的基本介绍 二、list 容器的成员函数 2.1 - 迭代器 2.2 - 修改操作 三、list 的模拟实现 3.1 - list.h 3.2 - 详解 list 容器的迭代器 3.2 - test.cpp   list 容器以类模板 listT(T 为存储元素的类型)的形式定义在 list 头文件中,并位于 std 命名空间中 。 list 是序列容器,允

    2024年02月12日
    浏览(39)
  • 【C++】学习STL中的list

            大家好!,今天为大家带来的一篇博客是关于STL中的list,内容主要包括list的介绍使用、list的模拟实现。以及list与vector的对比。         首先,让我们看看list的文档介绍: list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向

    2024年02月10日
    浏览(38)
  • 【C++学习】STL容器——list

    目录 一、list的介绍及使用 1.1 list的介绍  1.2 list的使用 1.2.1 list的构造  1.2.2  list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers 1.2.6 list 迭代器失效 二、list的模拟实现 2.1 模拟实现list 三、list和vector的对比 一、list的介绍及使用 1.1 list的介绍 list的文档介绍

    2024年02月14日
    浏览(38)
  • C++ list 模拟实现

      目录 1. 基本结构的实现 2.  list() 3. void push_back(const T val) 4. 非 const 迭代器 4.1 基本结构  4.2 构造函数  4.3 T operator*() 4.4  __list_iterator operator++() 4.5 bool operator!=(const __list_iterator it) 4.6 T* operator-() 5. const 迭代器  6. begin()  end() ​编辑 7. iterator insert(iterator pos, const T v

    2024年02月08日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包