【STL】序列式容器--list（简单复习）

落日映苍穹つ 2022-06-13 04:15 178阅读 0赞

【STL】常用容器总结，带有复习性质的学习更有效率；

--------------------

list 和 vector 是最常用的两个容器，也是在面试中最常被问到的，让你对比一下这两个容器；

那么，首先复习一下 list 的结构，list 底层的数据结构是双向链表，同时，和vector不同的是，list 的迭代器不再是原生指针， 而是专门封装的双向迭代器；

既然是链表，那么和 vector 一对比， 不同之处就很明显了， 首先因为是链表结构，所以插入和删除一个元素不再向 vector 那么费劲， 同时删除一个元素也不会造成大部分的迭代器失效，只有被删除的迭代器失效，插入完全不会影响迭代器；

这时候，就需要回顾到 vector 和 list 的适用场景了；

vector适合于频繁在尾部插入和删除元素的操作，而 list 则适合于频繁在中间进行插入和删除的操作，至于原因，我想，上面说的都很清楚了；

还有一点，就是vector相比于list不需要维护复杂的数据结构；当然vector可以支持下标的随机访问，而list 只能遍历；

list 还有一系列的api, 当然我们平常使用时只把它当做一个普通的链表来使用，并不会把它当做太复杂，其实，SGI 版的STL–list本质上是一个环状双向链表，不做研究；

这里演示一下list的插入和删除迭代器的处理；

#include<iostream>
    #include<list>
    using namespace std;
    
    int main()
    {
        list<int> L;
    
        for(int i = 0; i < 6; i++)
        {
            L.push_back(i);
        }
    
        list<int>::iterator it = L.begin();
    
        while(it != L.end())
        {
            if(*it == 2)
            {
                L.insert(it,2,1);
                //验证插入迭代器是否失效
            }
    
            it++;
        }
    
        it = L.begin();
        while (it != L.end())
        {
            cout<<*it<<" ";
            if(*it == 3)
            {
                L.erase(it++);
                //删除迭代器
            }
            else
            {
                it++;
            }
        }
        cout<<endl;
        return 0;
    }

分析：上面这个例子演示了如何正确使用list的插入和删除，通过例子我么可以看到，在迭代器指向2 的时候， 我们在它前面插入了两个1 ， 下面仍然使用迭代器++，在下图的最终结果中，程序正确运行，如果你自己实验的话，完全可以在插入之后打印迭代器内容，看看是不是还是指向2；

删除迭代器就像我们前面说的，list的迭代器只会失效被删除的那个，所以我们正确的处理方式就是在传参的时候迭代器后置++，这样就完美的越过了失效的迭代器，程序正确运行；

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220613/67e5352c7f754b4e804a770e2371a2e6.png