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.
