list上

发布时间:2024年01月19日

初步了解list

面试题:为什么会有list?

答:为了解决vector的缺点

vector的缺点:

插入数据需要挪动数据;
插入数据需要增容;
注:
vector和string都是数组,在哪个位置插入数据,后面的数据是要往后挪动位置的;所以时间复杂度是o(n);
而list是链表,插入数据时o(1);

vector、list优点

vector支持下标随机访问;
list头插尾插不需要挪动数据、效率高;并且不需要增容

list结构

本质是带头双向循环链表;
列表种类有哪些?
答:带头、不带头;循环、不循环;单向、双向;这样2^3组合种;
image.png
只要一个容器支持迭代器,就可以用范围for遍历;

迭代器的分类

从支持的接口角度:
单向(forward_list)、双向(list)、随机(vector);
一般从使用场景分类:
正向、反向、正向const、方向const;

list的简单运用

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<list>

using namespace std;

void print_list(const list<int>& l)
{
	list<int>::const_iterator it = l.cbegin();

	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

}



void test_vector1()
{
	list<int> l;
	l.push_back(1);
	l.push_back(1);
	l.push_back(1);
	l.push_back(1);
	l.push_back(1);
	l.push_back(1);

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

	//拷贝
	list<int> l1(l);
	print_list(l1);
}


void test_vector2()
{
	//insert、erase
	//vector的迭代器失效insert、erase都会、list只用erase会迭代器失效

	list<int> l1;
	l1.push_back(1);
	l1.push_back(20);
	l1.push_back(3);
	l1.push_back(5);
	l1.push_back(8);
	l1.push_back(10);

	print_list(l1);

	list<int>::iterator pos = find(l1.begin(), l1.end(), 20);//现在pos就是begin()开始往后面找,里面数值为20的迭代器
	l1.insert(pos, 22);
	for (auto e : l1)
	{
		cout << e << " ";
		e++;
	}
	cout << endl;

	l1.erase(pos);
	l1.insert(pos,11);
	print_list(l1);


}


int main()
{
	test_vector2();
	return 0; 
}

insert、erase、迭代器失效(和vector的区别)

插在这个pos位置
image.png

erase

1、这个pos的所指向的仍是指向20的这个迭代器没有变化,因为他是列表;
2、如果是vector或者string那么在insert之后再用pos会发生迭代器失效,为什么?
答:迭代器失效:因为insert之后pos所指向的内容发生了改变,vector和string本质是一个数组中间插入一个数后面数的位置都要改变、pos这个迭代器指向的地址上的内容改变了就会报错,如果发生了增容、那更加错了、增容的话原本这个数组的地址就变了;
而list是列表,列表和数组(数据结构上的内容),列表是里面存了一个数值、然后还存了一个指向下一个列表的指针,所以插入值后pos指向的位置始终不变、只是插入的新的这个数据里面有个指针指向了pos;
image.png
3、erase的话、list和vector都会存在迭代器失效
erase,list是这个pos迭代器,本质就是pos这个指针指向的空间被销毁了;
vector道理相似;
image.png

class和struct

struct和class是一样的,只是struct默认是public,class默认是private;
struct内数据默认是public类型的,class内数据默认是private类型的;
struct变量放在栈上,而class变量放在堆上,因此struct变量会自动释放,而class变量需要手动释放;

list的迭代器

是另一个struct出来的,不是列表里面的next和prev指针;
image.png
image.png
list::iterator it = lt.begin()

为什么这个迭代器的构造函数不用深拷贝?

描述:这个迭代器就不用深拷贝了,用默认的浅拷贝就行了
image.png
答:这里直接让他两指向同一个空间,不会像vector、string要深拷贝、比如v1(v2),这个v1、v2浅拷贝的话就是他们内部指针指的位置都一样了,那就是v1释放空间v2也没了,但是迭代器用不到这个功能;

tmp 是一个在函数内部创建的局部变量,但它的引用被返回给调用者。当函数执行完毕或者离开 tmp 的作用域时,tmp 对象本身并不会被销毁,因为它的引用仍然存在于调用者的上下文中。
这意味着,即使超出了包含 tmp 的作用域,tmp 对象仍然存在,并且可以通过返回的引用进行访问。只有当调用者不再使用返回的引用时,tmp 对象才会被销毁。

模拟list

注:

delete和delete[]区别是前者释放单个对象、后者释放数组对象

具体代码

写一个列表的结构体

构造函数以及其中的成员函数

	template<class T>
	//struct__list_node,两个_这种取名方式一般表示一会这个会在别的里面用,在这里就表示,list类里面直接用的类外面定义的struct __list_code这个结构体
	struct __list_node
	{
		__list_node<T>* _next; // 别忘了这里要写<T>
		__list_node<T>* _prev;
		T _data;

		//列表需要构造函数来初始化
		__list_node(const T& x = T())//这个T(),指的是没有传值过来那就直接为0
			:_data(x)
			,_next(nullptr)  
			,_prev(nullptr)
		{}
	};

迭代器

主要用到list里面的两个指针,分别指向前后_next、_prev;

	//struct迭代器__list_iterator
	template<class T>
	struct __list_iterator
	{
		typedef __list_node<T> Node;
		Node* _node;

		//构造函数,struct怎么写构造函数、就是看这个里面成员函数有哪些
		__list_iterator(Node* node)
			:_node(node)
		{}

		//构造传的是里面的成员函数、拷贝是传的类或者说这个结构体
		//浅拷贝,这个是默认函数、不用写的
		__list_iterator(const __list_iterator<T>& it)
		{
			_node = it._node;
		}

		// operator*,读_node中的data,data的类型是T,所以函数返回值类型是T
		T& operator*()
		{
			return _node->_data;
		}


		//++
		__list_iterator<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		__list_iterator<T> operator++(int) //后置++里面就放个int,这是设计出来的伪参数,用来区分前后置用的
		{
			__list_iterator<T> tmp(*this); //直接拷贝函数、这个不用写、因为是浅拷贝,深拷贝才要写
			_node = _node->_next; 
			//++(*this);
			return tmp;
		}

		//--
		__list_iterator<T>& operator--() 
		{
			_node = _node->_prev; //_node是指针
			return *this; //*this就是迭代器,this是指针指向迭代器
		}
		__list_iterator<T>& operator--(int) //后置++里面就放个int,这是设计出来的伪参数,用来区分前后置用的
		{
			__list_iterator<T> tmp(*this); //直接拷贝函数、这个不用写、因为是浅拷贝,深拷贝才要写
			//node = _node->_next;
			--(*this);
			return tmp;
		}




		//!=,两个迭代器之间不相等、迭代器里面的成员函数是_node,比的是这两个,就是他指向一个列表的地址,看这两个地址一样吗
		bool operator!=(const __list_iterator<T>& it)
		{
			return _node != it._node;
		}

		T* operator->()
		{
			return& _node->_data;//返回这个地址
			//指向这个地址,调用时第一个->返回其地址、第二个->返回地址上的值,迭代器做了优化,调用只需要一个->
		}


	};

class类

template<class T>
class list
{
	typedef __list_node<T> Node;
public:
	typedef __list_iterator<T> iterator; // 放public里面不然外面动不了T,就是用不了模板,私有的不能用

	//迭代器用节点的指针就行了
	iterator begin()
	{
		return iterator(_head->_next);
		//注意这里返回的是迭代器,不是_head头部指针、这个是list类里面的成员变量
		//现在是把头部指针_head传过去,然后迭代器调用他的拷贝函数;
		//这里面就是构造函数、因为传过去的是Node类型;
	}
	iterator end()
	{
		return iterator(_head);
	}

	//构造函数
	list()
	{
		_head = new Node;//new node //这里面不用写成Node[],是因为[]是数组用的,这个就里面就开辟一个指针指向的地址空间,[]是一个数组的空间
		_head->_next = _head;
		_head->_prev = _head;

	}

	void push_back(const T& x = T())
	{
		Node* tail = _head->_prev;
		Node* newnode = new Node(x);

		tail->_next = newnode;
		newnode->_prev = tail;
		newnode->_next = _head;
		_head->_prev = newnode; 
	}

private:
	Node* _head;
};


两个测试案例

	void test_list1()
	{
		list<int> lt;

		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

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

	}
	

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

	};

	void test_list2()
	{
		list<Date> lt;
		lt.push_back(Date());
		lt.push_back(Date());

		list<Date>::iterator it = lt.begin();//调用data,因为现在模板T就是date,传参传过去date是可以的
		while (it != lt.end())
		{
			cout << it->_year << " " << it->_month << " " << it->_day;
			++it;
		}
		cout << endl;
	}

报错

image.png
修改
image.png

文章来源:https://blog.csdn.net/user2604530353/article/details/135636450
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。