list上-初步了解list

时间：2024-01-21 09:28:14

面试题：为什么会有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.begin();

	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也没了，但是迭代器用不到这个功能；

相关文章