135-C++学习第九弹

2022-10-10 19:57:39

#include< array >//静态数组
#include< vector >//可以伸缩，放数组可以根据数据量动态申请大小
#include< list >//循环双链表
#include< forward_list >//单链表
#include< deque >//双端队列
#incldue< stack >//栈
#incldue< queue >//队列

list的介绍

可以正向，逆向迭代
每个节点通过malloc,new开辟
在频繁插入和删除下，用list比较好，比vector速度快得多
在频繁查询下，用vector比较好，list每个节点并不连续
数据量巨大的时候，vector比list寻找的容易的多
数据量巨大的情况下，选择vector的根本原因是：
vector数组：1.**数组元素挨着，没有浪费空间，而list链表有next,prev，还有头部信息等等，存储密度小 2.在操作系统上看，每个节点从堆区申请，随机的，堆区空间以4k为一页，vector的页与页之间是连续的，但是链表的话，这个结点是在这个页中存储的，但是它的next的可能在其他页，其他结点也可能在其他页中申请的，查询的时候，系统产生缺页的问题，导致内存缺页。缺页中断。vector找下一页时可能缺页中断。对于链表，找数据，也就是next找下一个位置和找页两个过程中，导致缺页中断。

存储密度，如果都是整型，存储密度就是三分之一（4+4+4）
实际上比三分之一小得多，实际上还有4个字节的上越界标记，下面有4个字节的下越界标记，最上面还有28个字节的头部信息（记录申请给用户的12个字节，还有其他的状态信息）还有堆区的管理者，还要耗损一定的空间
感觉申请了12个字节，实际上浪费了非常大的空间

_M_Size：记录双链表的结点的个数
begin():指的是的第一个结点，end()指的是最后一个结点的后继，即头结点
成员

打印list
迭代器


template<class _Ty>
class List
{
	struct _Node;
	typedef struct _Node* _Nodeptr;//结点的指针
	struct _Node
	{
		_Nodeptr _Prev,_Next;
		_Ty _Value;
	};
private:
	_Nodeptr _M_head;
	_Nodeptr _M_size;
	class iterator
	{
	public:
		iterator(_Nodeptr_P=nullptr):_Ptr(_P){}

		value_type& operator*(){return _Ptr->Value;}
		value_type* operator->(){return &_Ptr->Value;}
    protected:
		_Nodeptr _Ptr;
	};
};

使用
使用迭代器打印

int main()
{
	list<int>ar;
	list<int>br={12,23,34,45,67,78};
	//以下是用迭代器打印

	list<int>::iterator it=br.begin();
	for(;it!=br.end();++it)
	{
		cout<<*it<<endl;
	}
	return 0;
}

注意：list没有重载[]
但是vector可以用[]

使用方法2：

int main()
{
	list<int>ar;
	list<int>br={12,23,34,45,67,78};
    for(auto x:br)//br是容器，auto x提取容器里的元素类型
	{
		cout<<x<<endl;
	}
	return 0;
}

这两种方法有什么区别呢
对于内置类型，没有区别
对于自己设置的类型

链表可以从头插入，也可以尾部插入
对于vector只有从尾部插入，数据移动的问题

首先调用构造函数，产生一个Int对象，然后把这个对象传递给这个链表的push_back方法,构建一个结点，然后把这个对象初始化这个结点，调用的是移动构造，因为Int(i)是将亡值，无名。

调用拷贝构造函数进行构造，因为这里的a不是将亡值，有名字
打印

重点来了

对于list里面的库，都是有迭代器的
A:从容器里抽取数据，一个一个地给x
auto x 存在拷贝构造 ，效率最低

B：

这里不会出现拷贝构造
&x是别名

但是ar容器值的别名，++x，就是对容器的值修改了

C：

只能够读取，不能够修改，没有调动拷贝构造
D：

这里实际上没有调动移动构造，直接把ar里面的值给x，和上一个情况一样的，仍然是别名，也可以进行修改，只是右值引用而已，没有移动构造
因为对于ar，容器里的数据虽然无名但是占有空间，不是真正意义上的右值

移动构造，参数是右值才可以调动，而不是自身是右值要调动移动构造
a对象普通构造，a对象有名字，调用拷贝构造函数构造b对象

临时对象，无名，调用移动构造

c有名字，不是右值，右值不可以取地址

这里d

调式时发现

都没有调动移动构造
原因是编译器进行了优化，构建的无名对象就是c本身，不去调动移动构造

在这个地方，系统不会调动移动构造，编译器进行了优化，return 的对象就是c本身

这个情况产生了一个临时对象a作为过渡，系统进行了移动构造

首元素构建一个给x（拷贝构造）

实际上是容器首元素++

引用在系统里相当于指针
x所指对象已经被释放
现在的x是无效的，相当于空悬指针

对于容器元素，都是引用返回，但是接收时不要轻易引用接收！
如果以值接收，就是调用构造函数，构建x，就与容器里的对象没有关系了

const仍然不能约束pop_front的动作

一删除，这个迭代器就变成失效的迭代器，不能继续使用了

在迭代器之前插入一个Int(30),不会造成失效，迭代器指向并没有发生改变

那这个地方会不会失效呢？

在容器里
对于此情况，迭代器绝大可能会失效
迭代器相当于面向对象版本的指针
可能性比较大的情况下会失效，尽量不用
vector连续开辟空间，

插入40，但是没位置了，扩容（开辟新的空间，对象一个一个拷贝进去），把原空间删除，迭代器指向的位置没有数据了

使用vector插入，删除元素都有可能使迭代器失效，一旦扩容，内存在别的地方开辟
使用list插入没有影响，因为是一个一个结点，和之前的结点没有关系但是删除就失效