C++ STL list 容器常用接口与拓展用法详解

2.2、list 对象容量操作

void test2() { 
    list<int> lt({ 1,2,3,4,5 }); 
    cout << lt.size() << endl; 
    if (lt.empty()) cout << "为空" << endl; 
    else cout << "非空" << endl; 
}

2.3、list iterator（迭代器）

此处，大家可暂时将迭代器理解成一个指针，该指针指向 list 中的某个节点。

2.4、链表的增删查改

2.5、链表的遍历

由于 list 底层结构为双向链表，导致他的元素在内存中并不是连续存储的，所以我们不能用下标的方式来访问。

方法一：范围 for + auto

void test3() { 
    list<int> lt({ 1,2,3,4,5 }); 
    for (auto e : lt) { 
        cout << e << " "; 
    } 
}

方法二：迭代器

void test4() { 
    list<int> lt({ 1,2,3,4,5 }); 
    list<int>::iterator it = lt.begin(); 
    while (it != lt.end()) { 
        cout << *it << " "; 
        it++; 
    } 
}

3、拓展接口说明

3.1、尾插——emplace_back

前面我们已经介绍了一个尾插的接口（push_back），那为什么 list 容器还要实现一个 emplace_back 尾插接口呢？

假设我们额外定义一个 AA 类，然后，将 AA 类型的数据分别使用 push_back 和 emplace_back 尾插到 lt 对象，看会发生什么？

struct AA { 
    AA(int a1 = 1, int a2 = 1) :_a1(a1) ,_a2(a2) {} 
    int _a1; 
    int _a2; 
};

void test5() { 
    AA a1; 
    list<AA> lt; 
    lt.push_back(a1); 
    lt.push_back(AA(20, 20)); 
    lt.push_back(30, 30); // 报错 
}

这里有一种应用 emplace_back 特殊情景，此时只有 emplace_back 才能够实现。当我们想要直接将构造 a 对象的数据作为参数传给尾插函数时，push_back 就会报错，而 emplace_back 则支持这种操作。

// emplace_back 
void test6() { 
    list<AA> lt; 
    lt.emplace_back(30, 30); 
}

3.2、合并两个已排序的链表——merge

需要注意：merge 只能用来合并两个已经排好序的链表，同时，合并之后一个链表将会为空。

void test7() { 
    std::list<double> first, second; 
    first.push_back(3.1); 
    first.push_back(2.2); 
    first.push_back(2.9); 
    second.push_back(3.7); 
    second.push_back(7.1); 
    second.push_back(1.4); 
    // 保证有序 
    first.sort(); 
    second.sort(); 
    // 将已经有序的 second 合并到 first 链表 
    first.merge(second);// (second is now empty) 
    for (auto e : first) cout << e << " "; 
}

3.3、移除链表中连续的重复元素——unique

注意：只能连续的重复元素去掉，并只保留一个。

void test8() { 
    list<int> lt; 
    lt.push_back(1); 
    lt.push_back(5); 
    lt.push_back(5); 
    lt.push_back(4); 
    lt.push_back(5); 
    lt.push_back(6); 
    for (auto e : lt) cout << e << " "; 
    cout << endl; 
    lt.unique(); // 去重 
    for (auto e : lt) cout << e << " "; 
}

3.4、将一个链表的元素或元素范围移动到另一个链表的指定位置——splice

注意：移动之后一个链表将会为空。

void test9() { 
    std::list<int> mylist1, mylist2; 
    std::list<int>::iterator it; 
    for (int i = 1; i <= 4; ++i) mylist1.push_back(i); 
    for (int i = 1; i <= 3; ++i) mylist2.push_back(i * 10); 
    it = mylist1.begin(); 
    ++it; 
    mylist1.splice(it, mylist2); // 链表 mylist2 节点转移给链表 mylist1 的第二个节点之前 
    for (auto e : mylist1) { 
        cout << e << " "; 
    } 
}

3.5、链表元素的排序——sort

我们知道 C++ 在标准库中已经实现了排序算法，为什么 list 还要再自己实现呢？这就是因为迭代器的性质造成的。下面我们来介绍一下迭代器的类型。

根据前面对 string 和 vector 的学习，我们知道，根据迭代器的功能，将迭代器分为：

• iterator————普通对象
• const_iterator————const 对象
• reverse_iterator————普通对象的反向迭代器
• const_reverse_iterator————const 对象的反向迭代器

根据迭代器性质将迭代器分为：

• 按性质分为：（向上兼容）
  • 随机迭代器：string/vector/deque... 支持++ / -- / + / - ；
  • 双向迭代器：list/map/set... 支持++ / -- ；
  • 单向迭代器：forward_list/unordered_map 支持++

#include<algorithm> // sort 的头文件 
void test01() { 
    list<int> lt; 
    lt.push_back(6); 
    lt.push_back(3); 
    lt.push_back(5); 
    lt.push_back(2); 
    lt.push_back(1); 
    // sort :仅支持随机迭代器 
    //sort(lt.begin(), lt.end()); // list 类对象的迭代器为双向迭代器，所以报错 
    string st("ahdncxvjsvf"); 
    sort(st.begin(), st.end()); // string 类对象的迭代器为随机迭代器 
    cout << st << endl; 
    // reverse : 支持双向迭代器（也兼容随机迭代器） 
    reverse(lt.begin(), lt.end()); 
    reverse(st.begin(), st.end()); 
}

void test02() { 
    list<int> lt; 
    lt.push_back({6, 3, 5, 2, 1}); 
    // list 容器中的 sort 
    lt.sort(); 
    for (auto e : lt) cout << e << " "; 
}

4、总结

list 容器提供了丰富而且非常实用的接口，只要我们不断查文档，并不断应用，就一定能够掌握这些接口的用法。