企业官网建设流程全解析

1.list的使用

1.1构造函数

迭代器的功能

我们不难发现,之前在string和vector中都可以这样构造,但是到了list怎么就不行了呢?
根据报错推测,list似乎不允许这样使用迭代器.
我们进一步区分一下三者的迭代器:

这是string的迭代器,意为随机迭代器

这是vector的迭代器,同样是随机迭代器

这是list的迭代器,是双向迭代器.

可以看出来,迭代器是根据功能细分的.

• 单向迭代器(forward iterator):只支持单向.一趟的遍历,即只支持++操作.
• 双向迭代器(bidirectional iterator):比单向略微强大一点,支持正向反向操作,即++和–.
• 随机迭代器(random iterator):通常是顺序表类似的结构,支持自由.随机的访问,支持++,–,还有+和-
  还有一种比单项迭代器更弱的输入迭代器(input iterator),和单向迭代器一样都是只支持++操作,但是它是一次性的迭代器,不允许重复使用,想要再次使用需要更新.

因此,由于list的迭代器是双向的(list的底层结构是双向带头循环链表),不支持+和-操作,所以会报错

STL包含算法库,不同的算法要求的迭代器也不同.
迭代器具有继承关系,更强大的迭代器继承了稍弱迭代器的功能.这意味着如果一个算法要求使用单向迭代器,那么我们既可以传双向迭代器,也可以传随机迭代器.
例如:

逆置算法支持双向迭代器,可以传双向,随机,但是不能使用单向迭代器:

1.2尾插,尾删,头插,头删

1.3容器内提供的算法

sort

算法库中的sort只支持随机迭代器,所以list内部单独实现了一个sort排序算法,
像排序这样的指令都是在cpu执行的,cpu运行速度很快,但是内存的读取速度很慢,内存跟不上cpu的速度.
因此计算机中有了缓存设计,当cpu读数据时会把一大串数据加载到缓存中.如果能在缓存中找到i想要的数据称为cpu缓存命中,否则是缓存未命中.对于顺序表来说,一次读取一块数据到缓存中会提高效率,下一次读取大概率也能命中.而链表的物理结构是不连续的,即使读取一大块数据到缓存中也未必能命中下一个.相反还会因为这一大块无效数据污染缓存

所以在数据量小的时候勉强能使用sort,但是数据量大的时候就不能使用了,而是要把数据拷贝到顺序表结构中使用库中的sort,再拷贝回list.