C++ STL list 容器特性与常用接口解析

1.2 list 的使用

list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为 list 中一些常见的重要接口。list 的头插和头删复杂度都为 O(1)。

从 string 之后，position 都变了，在 string 的部分都是用下标去插入，现在的位置都是迭代器，但是和 vector 还是有点区别的。比如下面的在第五个位置插入数据：

int main()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_front(10);
    lt.push_front(20);
    //如果要在第五个位置插入数据
    //下面这种方法是不行的
    //lt.insert(lt.begin() + 5, 10);
    //因为 vector 是一个连续的物理空间，是支持 + 的，但是插入的代价比较大，数据要往后挪动。
    //list 和 vector 各有各的优缺点。
    //list 的物理空间不是连续的，可以支持 +，但是代价比较大，库立面没有直接支持。
    //只有一种方法
    auto it = lt.begin();
    for (size_t i = 0; i < 5; i++)
    {
        ++it;
    }
    lt.insert(it, 100);
    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

这是 vector 和 list 的第一个差别，这种差别是迭代器的差别导致的，list 的插入代价是很低的，把前后位置的指向关系改变一下就可以了，排序都写到算法里面去了。

还有一种插入的场景，就是找到一个值，在它的前面插入一个数据。list 和 vector 都没有提供 find 接口。

对于 vector 来说用小于没有问题，但对于 list 来讲，迭代器中 end() 节点的地址不一定比 begin() 大，end() 的节点是有效数据的下一个位置，也就是哨兵位。

list 中的 insert 接口不存在迭代器失效的问题，比如我要在这个位置插入接点，没有扩容的问题，没有野指针的问题，没有位置改变的问题，因为不需要挪动数据。vector 在这个位置插入之前有两大问题，第一大问题就是扩容，第二大问题就是插入这个数据之后，位置往后挪，它的位置意义都变了。

erase 节点存在迭代器失效的问题，因为节点都没了。

算法中的 find，找到就返回这个节点，找不到就返回 end 节点。

int main()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_front(10);
    lt.push_front(20);
    auto it = lt.begin();
    it = find(lt.begin(), lt.end(), 3);
    if (it != lt.end())
    {
        lt.insert(it, 3);
        *it *= 100;
    }
    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
    it = find(lt.begin(), lt.end(), 3);
    if (it != lt.end())
    {
        lt.insert(it, 30);
        *it *= 100;
    }
    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

如果是 erase 的话，程序就会崩溃：

int main()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_front(10);
    lt.push_front(20);
    auto it = lt.begin();
    it = find(lt.begin(), lt.end(), 3);
    if (it != lt.end())
    {
        lt.insert(it, 3);
        *it *= 100;
    }
    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
    it = find(lt.begin(), lt.end(), 3);
    if (it != lt.end())
    {
        lt.erase(it);
        *it *= 100;
    }
    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

如果要用 erase 删除 list 中的偶数：

int main()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_front(10);
    lt.push_front(20);
    auto it = lt.begin();
    //如果要用 erase 删除 list 中的偶数：
    while (it != lt.end())
    {
        if (*it % 2 == 0)
        {
            it = lt.erase(it);
        }
        else
        {
            ++it;
        }
    }
    for (auto e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

swap 就是两个链表直接交换。

int main()
{
    list<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    list<int> lt2;
    lt2.push_back(10);
    lt2.push_back(20);
    lt2.push_back(30);
    lt2.push_back(40);
    for (auto e : lt1)
    {
        cout << e << " ";
    }
    cout << endl;
    for (auto e : lt2)
    {
        cout << e << " ";
    }
    cout << endl;
    lt1.swap(lt2);
    for (auto e : lt1)
    {
        cout << e << " ";
    }
    cout << endl;
    for (auto e : lt2)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

容器都是通过迭代器区间去访问的，比如这有一个容器，想在这一段查找，给这个容器的区间查找这个 val 就可以了。

clear 就是把我们的节点删掉等等这些情况。

list 中 sort 的价值大不大，库里面也有一个 sort，list 中也提供了一个 sort，有啥意义呢？编译报错了，有时候掉不调到库里面去了，就看这个库是谁的归属，那就是哪儿出错了，sort 这个库用这个迭代器我们不能用，因为 sort 这个库里面用到一个

，就一个点我们就知道了，sort 是快排，快排不能用这个东西，因为快排要做过参数取中，参数取中选其中一个值的时候，选中间那个值或者选另外一个值的时候，我直接要选那个位置，快排不适合，就是那个链表没办法适应这个场景。

所以大家仔细再看，如果我们单看算法，这些算法的名字有一些差异，他这个是函数模板，但是他在这个名字上面很有讲究，它的名字就暗示了应该传什么迭代器，这里就要迁移出一个知识讲一讲，然后再结合这这个说，迭代器从他的功能的角度是会分类的，从功能上来说，分为单向、双向、随机。功能上是什么呢？单向就只能++，双向可以++也可以--，随机是可以++、--、也可以+，也可以 -。

谁的迭代器就是典型的单向呢？单链表、哈希表。谁是双向迭代器呢？双向链表，其实也就是我们的 list，还有 map、set，也就是树。谁是随机迭代器呢？vector、string、双端队列 deque。它这的名字就暗示了你用哪种算法，reverse 就适合用双向，find 就适合用单向，sort 就适合用随机。这个地方对迭代器是一个隐式的分类，可以认为它是一个性质进行划分，这个性质跟容器的底层结构有关系。

谁可以调用这个 sort 算法呢，这个 sort 底层是快排，决定了他要用这个随机迭代器，随机是可以吊的，链表就不可以调，链表这里调就报错了，用这个算法就要看容器的迭代器到底是哪一种，能不能适应，我怎么知道我的容器是哪一种呢？这里是有说明的，它的迭代器的内容是什么，vector 和 string 可以用这个逆置，随机迭代器可以认为是一个特殊的双向迭代器，随机迭代器满足双向的要求，满足单向的要求，

，如果写这个，单向、双向、随机都可以用，写随机的就随机可以用，写双向的就双向、随机可以用，写单向的就单向、双向、随机都可以用。

set 底层就是更复杂的迭代器，也就是树了，forward_list 是单向迭代器，

排序应该用 vector，不应该用 list，vector 的效率远高于 list，

数据量越大，差距越大一些，list 排序终究还是要慢不少。如果我们真的要数据排序，我们不应该用链表，链表访问数据相比 vector 毕竟还是慢，list 底层用的是归并算法。所以说 list 的 sort 意义不大。

void test_op()
{
    srand(time(0));
    const int N = 1000000;
    vector<int> v;
    v.reserve(N);
    list<int> lt1;
    //list<int> lt2;
    
    for (int i = 0; i < N; ++i)
    {
        auto e = rand();
        v.push_back(e);
        lt1.push_back(e);
    }
    // 排序
    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();
    int begin2 = clock();
    lt1.sort();
    int end2 = clock();
    printf("vector sort:%d\\n", end1 - begin1);
    printf("list sort:%d\\n", end2 - begin2);
}
int main()
{
    test_op();
    return 0;
}

list 的作用是当排序值比较小的时候，list 排序才有价值。

void test_op()
{
    srand(time(0));
    const int N = 100000;
    vector<int> v;
    v.reserve(N);
    list<int> lt1;
    list<int> lt2;
    
    for (int i = 0; i < N; ++i)
    {
        auto e = rand();
        lt2.push_back(e);
        lt1.push_back(e);
    }
    // 拷贝到 vector 排序，排完以后再拷贝回来
    int begin1 = clock();
    // 先拷贝到 vector
    for (auto e : lt1)
    {
        v.push_back(e);
    }
    // 排序
    sort(v.begin(), v.end());
    // 拷贝回去
    size_t i = 0;
    for (auto& e : lt1)
    {
        e = v[i++];
    }
    int end1 = clock();
    int begin2 = clock();
    lt2.sort();
    int end2 = clock();
    printf("vector sort:%d\\n", end1 - begin1);
    printf("list sort:%d\\n", end2 - begin2);
}
   
int main()
{
    test_op();
    return 0;
}

我们可以区分迭代器的类型，区分迭代器的类型有点复杂，叫做迭代器的萃取，就可以分辨出迭代器的类型。

merge 就是连个链表可以直接进行归并，归并有一个前提就是先有序，两个链表要先 sort 再 merge，这里还有另外一个东西叫仿函数，比较的仿函数的概念，仿函数在优先级队列再讲。

这个接口的本质是去重，去重也是有前提的，也是要先排序，如果不排序去重的话效率是很低的。

remove 就是 find 加 erase，remove 就是直接可以删。remove 唯一要注意的是如果这个值不存在会不会报错？

void text_x()
{
    int myints[] = { 17,89,7,14 };
    std::list<int> mylist(myints, myints + 4);
    mylist.remove(890);
    for (auto e : mylist)
    {
        cout << e << " ";
    }
    cout << endl;
}
int main()
{
    text_x();
    return 0;
}

相当于 find，如果找到就删除了，没找到就啥也不干。

remove_if 也涉及到一个仿函数的问题。

这个接口可以把一个链表的内容转移到另一个，它的转移是直接把节点拿走，就比如说有一个 a 链表，有一个 b 链表，直接把 a 链表的节点取下来直接插入到 b 链表，相当于 a 链表删除了数据，b 链表插入了数据，严格来说就是发生了转移。也可以转移到自己身上，但是别把范围区间重叠了。

int main()
{
    int myints[] = { 17,89,7,14 };
    std::list<int> mylist1, mylist2;
    std::list<int>::iterator it;
    for (int i = 1; i <= 4; ++i)
        mylist1.push_back(i);      // mylist1: 1 2 3 4
    for (int i = 1; i <= 3; ++i)
        mylist2.push_back(i * 10);   // mylist2: 10 20 30
    for (auto e : mylist1)
    {
        cout << e << " ";
    }
    cout << endl;
    for (auto e : mylist2)
    {
        cout << e << " ";
    }
    cout << endl << endl;
    it = mylist1.begin();
    ++it;
    // points to 2
    //全部转移
    //mylist1.splice(it, mylist2);
    //转移一个
    //mylist1.splice(it, mylist2, ++mylist2.begin());
    //部分转移
    //mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end());
    //把后面的数据转移到第一个的前面
    mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());
    for (auto e : mylist1)
    {
        cout << e << " ";
    }
    cout << endl;
    for (auto e : mylist2)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}