移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——7.list（模拟实现）

用户11286441

发布于 2024-09-23 19:33:15

420

发布于 2024-09-23 19:33:15

文章被收录于专栏：学习

1.前言

1.1list与vector的不同

区别：list的迭代器底层和其他两个迭代器底层有很大区别，因为list的链式结构决定了与它们两个的不一样相同：迭代器用法大致一样，其他成员函数的使用也大致一样。 vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下

1.2 迭代器的分类

例子：

可以得知list类型无法使用std中的sort函数，因为list的迭代器是双向的，而sort函数的迭代器参数是随机的，同理可以得出，string，vector，deque都可以使用std中的sort

1.3 list的本质

带头双向循环链表！！！！！！！！！！！！！！！！！！！

2.list节点

template<class T>//记得每一个类前要写模板
struct list_node       //struct和class一样均为类，不同的是struct中的所有成员均为公有（public）类型，可直接访问
{
	T data;
	list_node<T>* next;
	list_node<T>* prev;


	list_node(const T& x=T())  //const T& x=T()，在没有给值的情况下，系统会通过T（）自动生成一个类型匹配的值赋给x
		:data(x)
		,next(nullptr)
		,prev(nullptr)
	{}


};

用类来封装一个一个结点，里面有两个指针，一个是指向下一个位置的指针，一个是指向前一个位置，还有一个用来存放数据的变量

3.list类框架

template<class T>
class List
{
 public:
	typedef List_node<T> node;//取别名
    void empty_list()
	{
		head = new Node;
		head->_next = head;
		head->_prev = head;
	}
	List()//构造函数
	{
	    empty_list();
	}
 private:
     node*head;//头节点
     size_t _size;
}

list类里面包含的是结点的指针，也就是哨兵位头节点的指针

4.list迭代器

4.1 list迭代器框架

这里的迭代器是用封装加运算符重载来实现的，由于迭代器也会有很多类型，所以我们使用模板的形式

//T,T&,T*
//T,const T&,const T*        //设定了两种迭代器
template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数
struct list_iterator
{
	typedef list_node<T> node;
	typedef list_iterator<T,Ref,Ptr> self;
	node* node1;


	list_iterator(node* node2)
		:node1(node2)
	{}
}

4.2 list常用迭代器

//T,T&,T*
//T,const T&,const T*        //设定了两种迭代器

template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数
struct list_iterator
{
	typedef list_node<T> node;
	typedef list_iterator<T,Ref,Ptr> self;
	node* node1;


	list_iterator(node* node2)
		:node1(node2)
	{}

	self& operator++()
	{
		node1 = node1->next;
		return *this;           //模拟++
	}

	self& operator--()
	{
		node1 = node1->prev;
		return *this;           //模拟--
	}


	Ref operator*()
	{
		return node1->data;    //模拟指针解引用
	}


	Ptr operator->()
	{
		return &node1->data;
	}

	bool operator!=(const self& S)
	{
		return node1 != S.node1;
	}

};

迭代器的每一个操作都采用了运算符重载，其实这样看来还是指针在操作，只不过他不是直接的进行操作，而是换了一种方式

5.list函数详解

5.1插入和删除

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

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

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

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

iterator insert(iterator pos, const T& x)//在pos位置插入x
{
	node* it = pos.node1;
	node* newnode = new node(x);
	node* prev = it->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = it;
	it->prev = newnode;

	++_size;

	return iterator(newnode);                    //返回新插入的元素的位置
}

iterator erase(iterator pos)
{
	node* it = pos.node1;
	node* prev = it->prev;
	node* next = it->next;

	delete it;
	prev->next = next;
	next->prev = prev;
	--_size;

	return iterator(next);       //返回删除后的当前位置
}

5.2 拷贝构造和赋值运算符重载

list(const list<T>& it)    //i1(i2)
{
	int i = 0;
	empty_list();  //初始化列表
	for (auto e : it)  //相当于自动调用迭代器，并解引用，最后迭代器再++
	{
		i = 1;
		push_back(e);
	}

}


void swap(list<T>& it)
{
	std::swap(head, it.head);
	std::swap(_size, it._size);
}

list operator=(list<T>it)// i1=i2      传参直接调用拷贝构造
{
	swap(it);
	return *this;
}


size_t size()
{
	return _size;
}

5.3 list析构函数

~list()
{
	clear();
	delete head;
	head = nullptr;

}

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

}

6.打印函数

//打印
template<typename Container>
void print_container(const Container& con)
{
	typename Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

这里用的是typename，原因在于编译器在编译的时候，会去Container里面去找const_iterator这个类型，但是Container是一个模板，并没有实例化，所以编译器也不知道怎么定义，所以就在编译的时候就过不了，但是我们在前面加一个typename就会告诉编译器，先过，后面再来实例化，这样就可以解决问题了

适用于不知道list<T>中的T到底是什么类型时统一调用打印函数

7.代码总览

namespace zone
{
	template<class T>//记得每一个类前要写模板
	struct list_node       //struct和class一样均为类，不同的是struct中的所有成员均为公有（public）类型，可直接访问
	{
		T data;
		list_node<T>* next;
		list_node<T>* prev;


		list_node(const T& x=T())  //const T& x=T()，在没有给值的情况下，系统会通过T（）自动生成一个类型匹配的值赋给x
			:data(x)
			,next(nullptr)
			,prev(nullptr)
		{}


	};     

	//T,T&,T*
	//T,const T&,const T*        //设定了两种迭代器
	template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数
	struct list_iterator
	{
		typedef list_node<T> node;
		typedef list_iterator<T,Ref,Ptr> self;
		node* node1;


		list_iterator(node* node2)
			:node1(node2)
		{}

		self& operator++()
		{
			node1 = node1->next;
			return *this;           //模拟++
		}

		self& operator--()
		{
			node1 = node1->prev;
			return *this;           //模拟--
		}

		

		Ref operator*()
		{
			return node1->data;    //模拟指针解引用
		}


		Ptr operator->()
		{
			return &node1->data;
		}

		bool operator!=(const self& S)
		{
			return node1 != S.node1;
		}

	};

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




			void empty_list()
			{
				head = new node;
				head->next = head;
				head->prev = head;
				_size = 0;
			}//建立头节点

			list()
			{
				empty_list();  //初始化列表
			}

			~list()
			{
				clear();
				delete head;
				head = nullptr;

			}

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

			}

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

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

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

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

			iterator insert(iterator pos, const T& x)//在pos位置插入x
			{
				node* it = pos.node1;
				node* newnode = new node(x);
				node* prev = it->prev;
				prev->next = newnode;
				newnode->prev = prev;
				newnode->next = it;
				it->prev = newnode;

				++_size;

				return iterator(newnode);                    //返回新插入的元素的位置
			}

			iterator erase(iterator pos)
			{
				node* it = pos.node1;
				node* prev = it->prev;
				node* next = it->next;

				delete it;
				prev->next = next;
				next->prev = prev;
				--_size;

				return iterator(next);       //返回删除后的当前位置
			}


			list(const list<T>& it)    //i1(i2)
			{
				int i = 0;
				empty_list();  //初始化列表
				for (auto e : it)  //相当于自动调用迭代器，并解引用，最后迭代器再++
				{
					i = 1;
					push_back(e);
				}

			}


			void swap(list<T>& it)
			{
				std::swap(head, it.head);
				std::swap(_size, it._size);
			}

			list operator=(list<T>it)// i1=i2      传参直接调用拷贝构造
			{
				swap(it);
				return *this;
			}


			size_t size()
			{
				return _size;
			}
			
	    private:
			node* head;
			size_t _size;

	};


	void test()
	{
		list<int> arr; //调用class里的初始化列表
		arr.push_back(1);
		arr.push_back(2);
		arr.push_back(3);
		arr.push_back(4);
		arr.push_back(5);
		arr.pop_back();

		int i = 0;

		list<int> brr(arr);
		for (auto e : brr)
		{
			i = 1;
			cout << e << ' ';
		}

	}

}

8.杂谈

            iterator begin()              //可读可写
			{
				return iterator(head->next);  //原文写的是匿名对象，也可以写成return head->next
			}


			iterator end()
			{
				return iterator(head);       //原文写的是匿名对象，也可以写成return head
			}

思考：为啥可以这么改写？
1.单参数构造函数支持隐式类型转换，构造函数如下：

list_iterator(node* node2)
			:node1(node2)
		{}

2.函数返回需要调用拷贝构造，可理解为iterator（const iterator&it）//const可加可不加 3.但是return的是node*类型数据，不是iterator类型，这时因为存在一个单参数的构造函数 list_iterator(node* node2)，编译器会将node*数据隐式转换为iterator类型对象再调用拷贝构造
！！！！！！！！！！！！！类似string(const char* str); string s1 = “hello world”; 字符指针隐式类型转换为string。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-31，如有侵权请联系 cloudcommunity@tencent.com 删除

c++