首页 > 编程语言 >C++:模拟实现STL的list

C++:模拟实现STL的list

时间：2024-11-08 10:51:30浏览次数：7  
标签：node head iterator STL list C++ next prev

目录

一.list类

1.list的创建节点

2.list迭代器的运算符操作

3.list的构造函数及析构

4.list的迭代器

5.list的插入及删除

二.整体代码

1.list.h

2.list.cpp

在上一节已经了解list在库中的用法,在这里实现list的底层逻辑

一.list类

1.list的创建节点

template<class T>
struct __list_node
{
	__list_node* _next;
	__list_node* _prev;
	T _data;

	__list_node(const T& x = T()) :_data(x), _next(nullptr), _prev(nullptr) {}
};

2.list迭代器的运算符操作

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) {}
	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp(*this);
		//_node = _node->_next;
		++(*this);
		return tmp;
	}

	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		//_node = _node->_prev;
		--(*this);
		return tmp;
	}

	bool operator!=(const Self& it) 
	{
		return _node != it._node;
	}

	bool operator==(const Self& it) 
	{
		return _node == it._node;
	}
};

3.list的构造函数及析构

1.list的构造函数

因为list是双向带头循环链表,所以我们只需要让头节点的prev和next都指向头节点

//双向带头循环链表
list()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}

2.list的拷贝构造

拷贝构造时我们需要创建一个新的节点,将值依次插入尾部即可,可以通过迭代器遍历,也可以通过范围for

list(const list<T>& lt)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

	/*const_iterator it = lt.begin();
	while (it != lt.end())
	{
		push_back(*it);
		++it;
	}*/
	for (auto ch : lt)
		push_back(ch);
}

3.list的赋值

赋值是不需要创建新节点的,因为已经有了,所以只需要插入值即可

list<T>& operator=(const list<T>& lt)
{
	if (this != &lt)
	{
		clear();
		for (auto ch : lt)
			push_back(ch);
	}
	return *this;
}

4.list的析构

析构在这里我们用到clear函数,clear是清空所以数据,只留头节点,但是析构头节点也要释放

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		erase(it++);
	}
}

4.list的迭代器

iterator begin() 
{
	return iterator(_head->_next);
}

iterator end() 
{
	return iterator(_head);
}

const_iterator begin() const
{
	return const_iterator(_head->_next);
}

const_iterator end() const
{
	return const_iterator(_head);
}

5.list的插入及删除

push_back

尾部插入一个值时只需要将节点前后连接,并更新头节点的prev

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

任意插入一个值,我们需要创建一个节点,并将其与前后节点连接

void insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);
	//prev newnode cur
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
}

当我们实现了insert后,对于push_back和push_front都可以通过调用insert实现

	void push_back(const T& x)
	{
		insert(end(), x);
	}

	void push_front(const T& x)
	{
		insert(begin(), x);
	}

erase

对于erase来说,我们只需要找到删除节点的prev和next,将他们两个连接,删除当前节点即可

void erase(iterator pos)
{
	assert(pos != end());

	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	delete cur;

	prev->_next = next;
	next->_prev = prev;
}

实现erase后,pop_back和pop_front调用erase即可

void pop_back()
{
	erase(--end());
}

void pop_front()
{
	erase(begin());
}

二.整体代码

1.list.h

#pragma once
#include <iostream>
#include<assert.h>
using namespace std;

namespace wzyl
{
	template<class T>
	struct __list_node
	{
		__list_node* _next;
		__list_node* _prev;
		T _data;

		__list_node(const T& x = T()) :_data(x), _next(nullptr), _prev(nullptr) {}
	};

	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) {}
		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			//_node = _node->_next;
			++(*this);
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			//_node = _node->_prev;
			--(*this);
			return tmp;
		}

		bool operator!=(const Self& it) 
		{
			return _node != it._node;
		}

		bool operator==(const Self& it) 
		{
			return _node == it._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 iterator(_head->_next);
		}

		iterator end() 
		{
			return iterator(_head);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		//双向带头循环链表
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			/*const_iterator it = lt.begin();
			while (it != lt.end())
			{
				push_back(*it);
				++it;
			}*/
			for (auto ch : lt)
				push_back(ch);
		}

		list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (auto ch : lt)
					push_back(ch);
			}
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++);
			}
		}

		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 pop_back()
		{
			erase(--end());
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		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 newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}

		void erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;

			prev->_next = next;
			next->_prev = prev;
		}
	private:
		Node* _head;
	};

	void test_list1()
	{
		list<int> ls;
		ls.push_back(1);
		ls.push_back(2);
		ls.push_back(3);
		ls.push_back(4);

		list<int>::iterator it = ls.begin();
		while (it != ls.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	struct Date
	{
		int _year = 0;
		int _month = 1;
		int _day = 1;
	};

	void test_list2()
	{
		list<Date> ls;
		ls.push_back(Date());
		ls.push_back(Date());
		list<Date>::iterator it = ls.begin();
		while (it != ls.end())
		{
			cout << it->_year << "-" << it->_month << "-" << it->_day << endl;
			++it;
		}
		cout << endl;
	}

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void test_list3()
	{
		list<int> ls;
		ls.push_back(1);
		ls.push_back(2);
		ls.push_back(3);
		ls.push_back(4);
		ls.insert(ls.begin(), 0);
		ls.push_front(-1);
		print_list(ls);

		ls.pop_front();
		ls.pop_back();
		print_list(ls);

		ls.clear();
		ls.push_back(1);
		print_list(ls);
	}

	void test_list4()
	{
		list<int> lst1;
		lst1.push_back(1);
		lst1.push_back(2);
		lst1.push_back(3);
		lst1.push_back(4);

		list<int> lst2(lst1);
		print_list(lst2);

		list<int> lst3;
		lst3.push_back(10);
		lst3.push_back(20);
		lst3.push_back(30);
		lst3.push_back(40);
		lst1 = lst3;
		print_list(lst1);
	}
}

2.list.cpp

#include"list.h"

int main()
{
	wzyl::test_list1();
	//wzyl::test_list2();
	//wzyl::test_list3();
	//wzyl::test_list4();
	return 0;
}

标签：node,head,iterator,STL,list,C++,next,prev
From： https://blog.csdn.net/w200514/article/details/143609630

相关文章

  • C++入门基础（一）
    目录C++关键字命名空间命名冲突例子域的概念理解命名空间定义例子1例子2例子3例子4例子5例子6例子7C++输出与输入输出输入感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接......
  • C++解倒三角问题
    题目描述输入一个整数打印数字图形。输入一个整数（0<n<10）输出一个数字图形样例输入 3样例输出 关于本题代码如下：#include<iostream>usingnamespacestd;intmain(){ intn,k,t=1; cin>>n;k=n; for(inti=1;i<=n;i++......
  • c++解修剪花圃问题
    C++解“修剪花圃”题目描述你知道吗？在外国，如果你不修剪你的花圃，是要被贴罚单的。Xman忙于战斗，被贴了好多罚单。这一次好不容易休息了，他决定修剪一下。修剪成什么样子呢？当然是X形。Xman的花圃是一个n*n的正方形，其中n为大于等于3的正奇数。在每个位置上都有几个植物，对应的......
  • C++总结
    目录一、面向对象的三大特性二、引用2.1概念2.2特性三、类与对象3.1概念3.2类的内容3.3对象的创建四、构造函数与析构函数五、封装六、继承6.1概念与基础使用6.2继承权限6.2.1权限修饰符6.2.2继承权限6.3构造函数6.3.1派生类与基类的构造函数关系6.3......
  • 帝国CMS列表页模板list.var中调用栏目名称非栏目别名的方法
    方法一：勾选“使用程序代码”。在list.var中添加以下代码：$listtemp='<li>【'.$class_r[$r['classid']]['classname'].'】<ahref="[!--titleurl--]">[!--title--]</a>[!--newstime--]</li>';......
  • 【C++11】智能指针
    一.为什么需要智能指针        学习C++的人，一直在接触裸指针，一边感受着它的强大，一边感受着它的坑爹。当然，坑不坑爹在于开发者，指针本身近乎完美，但奈何用的人比较猥琐，给自己埋下无数的坑，还哭喊着指针不好用，那么今天要介绍的智能指针可以释放大家在使用裸指针时的一些压......
  • 【C++】C++11之函数对象，Lambda表达式和functional函数对象类型
    知识的学习在于点滴记录，坚持不懈函数对象        重载了函数调用运算符()的类的对象，即为函数对象。        std::function由上文可以看出：由于可调用对象的定义方式比较多，但是函数的调用方式较为类似，因此需要使用一个统一的方式保存可调用对象或者传递可......
  • C++循环引用指的是什么，在使用过程当中需要注意什么问题
    C++中的循环引用是指两个或多个对象相互持有对方的引用，导致这些对象无法被自动释放，从而造成内存泄漏。循环引用主要发生在使用智能指针（如 std::shared_ptr）管理对象生命周期时。以下是循环引用的具体解释及其使用中需要注意的问题：循环引用的形成当两个对象A和B互相持......
  • C++ 委托实现
    MyDelegate.h#pragmaonce#include<typeinfo.h>#include<list>#include<vector>namespaceDelegate{ //IDelegate提供接口的基类 template<typenameReturnType,typename...ParamType> classIDelegate { public: IDelegate(){} ......
  • C++之map容器
    map是C++STL(StandardTemplateLibrary)中的一种关联容器，用于存储键值对（key-valuepairs）。每个键（key）在map中都是唯一的，并且键值对会根据键的值进行排序（默认为升序）。map的内部实现通常为红黑树，因此它提供了高效的插入、删除和查找操作。主要特点键的唯一性：每个键在 ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99