【C++】list的模拟实现

03-05 阅读 0评论

文章目录

    • 1.list 底层
    • 2. list的模拟实现
      • 1. list_node 类设计
      • 2. list类如何调用类型
      • 3 .push_back(正常实现)
      • 4. 迭代器的实现
        • 第一个模板参数T
        • const迭代器
        • 第二个模板参数Ref
        • 第三个模板参数Ptr
        • 对list封装的理解
        • 5. insert
        • 6.push_back与 push_front(复用)
        • 7. erase
        • 8. pop_back与pop_front (复用)
        • 9. clear 清空数据
        • 10. 迭代器区间构造
        • 12. 拷贝构造
          • 传统写法
          • 现代写法
          • 13. 赋值
          • 3.完整代码

            1.list 底层

            list为任意位置插入删除的容器，底层为带头双向循环链表

            【C++】list的模拟实现,【C++】list的模拟实现,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,访问,第1张
            （图片来源网络，侵删）
            【C++】list的模拟实现

            begin() 代表第一个结点，end()代表最后一个结点的下一个

            2. list的模拟实现

            1. list_node 类设计

            template
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _data;
	};
            【C++】list的模拟实现

            C++中，Listnode作为类名，而next和prev都是类指针，指针引用成员时使用->，而对象引用成员时使用 .

            通过显示实例化，将两个类指针指定类型为T

            2. list类如何调用类型

            【C++】list的模拟实现

            Listnode 代表类型

            Listnode 代表类名 + 模板参数 才是类型

            而_head 以及创建新节点前都需加上类型

            【C++】list的模拟实现,【C++】list的模拟实现,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,访问,第5张
            （图片来源网络，侵删）

            3 .push_back(正常实现)

            void push_back(const T&x)//尾插
        {
            node* newnode = new node(x);
            node* tail = _head->_prev;
            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }
            【C++】list的模拟实现

            当我们想要创建一个节点时，需要调用node的构造函数

            typedef list_node node ，node是由 list_node 类提供的

            list_node(const T& x=T())//list类的构造函数
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{
		}

            最好在构造函数处提供全缺省，对于内置类型int可以使用0，但对于自定义类型来说就不可以，所以为了满足泛型的要求，使用匿名对象调用默认构造函数

            4. 迭代器的实现

            【C++】list的模拟实现

            若在数组上有一个int类型的指针，解引用是int类型的数据，再++可以加载下一个位置，因为物理空间是连续的

            【C++】list的模拟实现

            同样若在链表上，解引用类型为 node，再++不能到下一个节点，因为物理空间不连续

            所以构造迭代器通过封装节点的指针来进行构造 (后面会讲)

            【C++】list的模拟实现,【C++】list的模拟实现,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,访问,第9张
            （图片来源网络，侵删）
            第一个模板参数T

            创建一个_list_iterator的类，来实现迭代器功能

            template
    struct _list_iterator
    {
        typedef list_node node;
        typedef _list_iterator self;
        node* _node;
        
        _list_iterator(node* n)
            :_node(n)
        {
        }
        T& operator*()//解引用 
        {
            return _node->_data;
        }
        _list_iterator& operator++()//返回迭代器
        {
            _node = _node->_next;//指向下一个节点
            return *this;
        }
        bool operator!=(const self&s)
        {
            return _node != s._node;
        }
    };

            在list类中，调用迭代器实现begin()和end()功能

            typedef _list_iterator iterator，

            通过typedef 将_list_node类模板定义为iterator

            iterator begin()
		{
			return iterator(_head->_next);//通过匿名对象访问第一个数据
		}
		iterator end()
		{
			return iterator(_head);//通过匿名对象访问最后一个数据的下一个
		}

            在list类中实现begin()和end()，内部调用_list_node类的构造函数

            【C++】list的模拟实现

            const迭代器

            【C++】list的模拟实现

            假设第一个代表的是T * ，而第二个代表的 T * const，保护迭代器本身不可以被修改，而我们想要保护迭代器指向的内容不可被修改即 const T*

            复制_list_iterator类中的内容，并将名字修改为const_list_iterator

            只需修改*operator类型为cosnt T& ，说明解引用后的数据返回不能被修改

            template
    struct _list_const_iterator
    {
        typedef list_node node;
        typedef _list_const_iterator self;
        node* _node;
        _list_const_iterator(node* n)
            :_node(n)
        {
        }
        const T& operator*()//解引用 
        {
            return _node->_data;
        }
        self& operator++()//前置++
        {
            _node = _node->_next;//指向下一个节点
            return *this;
        }
        self& operator++(int)//后置++
        {
            self ret = *this;
            _node = _node->_next;
            return ret;
        }
        self& operator--()//前置--
        {
            _node = _node->_prev;
            return *this;
        }
        self& operator--(int)//后置--
        {
            self ret = *this;
            _node = _node->_prev;
            return ret;
        }
        bool operator!=(const self& s)//!=
        {
            return _node != s._node;
        }
        bool operator==(const self& s)//==
        {
            return _node == s._node;
        }
    };

            【C++】list的模拟实现

            第二个模板参数Ref

            迭代器和const迭代器只有 *operator 的返回值不同，

            只需在模板中添加一个参数即可使用一个迭代器实现迭代器和const 迭代器的功能

            【C++】list的模拟实现

            【C++】list的模拟实现

            第三个模板参数Ptr

            对于内置类型int使用解引用找到对应数据，而自定义类型需使用->寻找下一个节点

            【C++】list的模拟实现

            AA作为自定义类型，想要找到下一个节点需要使用->，在迭代器中 重载 - >

            it->_a1，实际上是 it->->_a1，

            it->返回值为AA* ,再通过这个指针使用->指向_a1

            但是为了增强可读性，省略了一个->

            it->_a1 实际上为 it.operator->()->._a1

            【C++】list的模拟实现

            【C++】list的模拟实现

            对list封装的理解
            【C++】list的模拟实现

            在不考虑封装的情况下，两者等价

            【C++】list的模拟实现

            从物理空间上来看，it与pnode都是指向1的地址

            【C++】list的模拟实现

            pnode作为一个原生指针，解引用指针就会拿到这个地址，找到这个地址指向空间的内容

            ++pnode，找到下一个节点的地址，但是下一个节点不一定是要的节点

            *it 识别成为自定义类型就会调用函数

            5. insert

            void insert(iterator pos,const T&x)//在pos位置前插入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;
        }
            【C++】list的模拟实现【C++】list的模拟实现

            6.push_back与 push_front(复用)

            两者都可以通过复用 insert的方式实现

            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);
        }

            7. erase

            void erase(iterator pos)//删除pos位置
        {
            //头节点不可以删除
            assert(pos != end());
            node* cur = pos._node;
            node* prev = cur->_prev;
            node* next = cur->_next;
            prev->_next = next;
            next->_prev = prev;
            delete cur;
        }
            【C++】list的模拟实现

            由于头节点不可以删除，所以使用assert断言的方式

            8. pop_back与pop_front (复用)

                            void pop_back()//尾删
        {
            erase(--end());
        }
        void pop_front()//头删
        {
            erase(begin());
        }

            9. clear 清空数据

            void clear()//清空数据
            //但是要注意不要把head清掉
        {
            iterator it = begin();
            while (it != end())
            {
                it=erase(it);//为了防止迭代器失效设置返回值
                 //返回值为当前节点的下一个
            }
        }

            迭代器失效是指迭代器所指向的节点失效 即节点被删除了

            erase函数执行后，it所指向的节点被删除，因此it无效，在下一次使用it时，必须先给it赋值

            【C++】list的模拟实现

            为了防止迭代器失效所以使erase设置返回值，返回值为当前节点的下一个

            10. 迭代器区间构造

            void empty_init()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
template 
		list(Iterator first, Iterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

            想要尾插的前提时，需要有头节点的存在，所以设置一个函数对头节点初始化

            12. 拷贝构造

            传统写法
            void empty_init()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
list(const list& It)//拷贝构造  传统写法
        {
            empty_init();//初始化头节点
            for (auto e : It)
            {
                push_back(e);
            }
        }
            【C++】list的模拟实现
            现代写法
            void swap(list& tmp)
        {
            std::swap(_head, tmp._head);
        }
        list(const list& It)//拷贝构造现代写法
        {
            empty_init();//将头节点初始化
            list tmp(It.begin(), It.end());
            swap(tmp);
        }

            通过调用std中的swap来达到交换的目的

            13. 赋值

            void swap(list& tmp)
		{
			std::swap(_head, tmp._head);
		}
list& operator=(list It)
        {
            swap(It);
            return *this;
        }

            参数不可以使用 list &，虽然可以达到赋值的目的，但是It的值也会发生改变

            【C++】list的模拟实现

            【C++】list的模拟实现

            3.完整代码

            #include
#include
#include
using namespace std;
namespace yzq
{
	template
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _data;
		list_node(const T& x=T())//构造函数
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{
		}
	};
	//迭代器
	template
	struct _list_iterator
	{
		typedef list_node node;
		typedef _list_iterator self;
		node* _node;
		_list_iterator(node* n)
			:_node(n)
		{
		}
		Ref operator*()//解引用 
		{
			return _node->_data;
		}
		Ptr operator->()//->
		{
			return &_node->_data;
		}
		self& operator++()//前置++
		{
			_node = _node->_next;//指向下一个节点
			return *this;
		}
		self& operator++(int)//后置++
		{
			self ret = *this;
			_node = _node->_next;
			return ret;
		}
		self& operator--()//前置--
		{
			_node = _node->_prev;
			return *this;
		}
		self& operator--(int)//后置--
		{
			self ret = *this;
			_node = _node->_prev;
			return ret;
		}
		bool operator!=(const self&s)//!=
		{
			return _node != s._node;
		}
		bool operator==(const self& s)//==
		{
			return _node == s._node;
		}
	};
	//const迭代器
	//template
	//struct _list_const_iterator
	//{
	//	typedef list_node node;
	//	typedef _list_const_iterator self;
	//	node* _node;
	//	_list_const_iterator(node* n)
	//		:_node(n)
	//	{
	//	}
	//	const T& operator*()//解引用 
	//	{
	//		return _node->_data;
	//	}
	//	self& operator++()//前置++
	//	{
	//		_node = _node->_next;//指向下一个节点
	//		return *this;
	//	}
	//	self& operator++(int)//后置++
	//	{
	//		self ret = *this;
	//		_node = _node->_next;
	//		return ret;
	//	}
	//	self& operator--()//前置--
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	self& operator--(int)//后置--
	//	{
	//		self ret = *this;
	//		_node = _node->_prev;
	//		return ret;
	//	}
	//	bool operator!=(const self& s)//!=
	//	{
	//		return _node != s._node;
	//	}
	//	bool operator==(const self& s)//==
	//	{
	//		return _node == s._node;
	//	}
	//};
	template 
	class list
	{
		typedef list_node node;
	public:
		typedef _list_iterator iterator;
		typedef _list_iterator const_iterator;//const迭代器
		//typedef _list_const_iterator const_iterator;
		void empty_init()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list()//构造函数
		{
			empty_init();
		}
		template 
		list(Iterator first, Iterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//list(const list& It)//拷贝构造
		//{
		//	empty_init();//初始化头节点
		//	for (auto e : It)
		//	{
		//		push_back(e);
		//	}
		//}
		void swap(list& tmp)
		{
			std::swap(_head, tmp._head);
		}
		list(const list& It)//拷贝构造现代写法
		{
			empty_init();//将头节点初始化
			list tmp(It.begin(), It.end());
			swap(tmp);
		}
		list& operator=(list It)//赋值
		{
			swap(It);
			return *this;
		}
		~list()//析构函数
		{
			//将头节点也要释放掉
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()//清空数据
			//但是要注意不要把head清掉
		{
			iterator it = begin();
			while (it != end())
			{
				it=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 push_front(const T&x)//头插
		{
			insert(begin(), x);
		}
		void insert(iterator pos,const T&x)//在pos位置前插入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;
		}
		iterator erase(iterator pos)//删除pos位置
		{
			//头节点不可以删除
			assert(pos != end());
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return iterator(next);
		}
		void pop_back()//尾删
		{
			erase(--end());
		}
		void pop_front()//头删
		{
			erase(begin());
		}
		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);
		}
	private:
		node* _head;
	};
	
	/*void test(const list&e)
	{
		list::const_iterator it = e.begin();
			while (it != e.end())
			{
					cout 
	//	list
	//		cout 
	//	list
	//		cout 
	//		cout 
	//	list
	//		cout 
	//		cout 
		list
			cout 
			cout 
	yzq::test4();
	return 0;
}

相关阅读：

1、访问者模式(大话设计模式)C/C++版本

2、访问者模式（Visitor Pattern）

3、【VUE实战项目】使用typescript重构项目

4、【VUE】10、VUE项目中多环境管理使用

5、Ubuntu 修改~/.bashrc终端选择是否使用annconda环境

免责声明
本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

发表评论

快捷回复： 表情：
评论列表 （暂无评论，人围观）

还没有评论，来说两句吧...

目录[+]