C++中的List

摘要

C++ 标准库中的 `std::list` 是一种双向链表容器，它允许在常数时间内进行插入和删除操作，每个元素包含一个指向前一个和后一个元素的指针。这给我们开发提供了高效的插入和删除操作。

引入头文件

要使用 `std::list`，需要包含头文件 ``：

#include 

创建和初始化

#include 
#include 
 
int main() {
    std::list<int> l1;                      // 默认构造函数
    std::list<int> l2(5, 10);               // 创建包含 5 个值为 10 的元素的列表
    std::list<int> l3 = {1, 2, 3, 4, 5, 6}; // 列表初始化
 
    // 输出列表 l3 的内容
    for (int n : l3) {
        std::cout << n << ' ';
    }
    std::cout << std::endl;
 
    return 0;
}

常用方法和操作

1. 插入和删除元素

#include 
#include 
 
int main() {
    std::list<int> l = {1, 2, 3, 4, 5, 6};
 
    // 在末尾添加元素
    l.push_back(6);
    // 在开头添加元素
    l.push_front(0);
 
    // 在第三个位置插入元素
    auto it = l.begin();
    std::advance(it, 3); // 前进 3 个位置
    l.insert(it, 99);
 
    // 删除开头的元素
    l.pop_front();
    // 删除末尾的元素
    l.pop_back();
 
    // 删除特定位置的元素
    it = l.begin();
    std::advance(it, 2); // 前进 2 个位置
    l.erase(it);
 
    // 输出列表 l 的内容
    for (int n : l) {
        std::cout << n << ' ';
    }
    std::cout << std::endl;
 
    return 0;
}

2. 访问元素

`std::list` 不支持随机访问（即不支持 `operator[]`），但是可以使用迭代器遍历和访问元素：

#include 
#include 
 
int main() {
    std::list<int> l = {1, 2, 3, 4, 5, 6};
 
    // 使用迭代器遍历
    for (auto it = l.begin(); it != l.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;
 
    // 使用范围 for 循环遍历
    for (int n : l) {
        std::cout << n << ' ';
    }
    std::cout << std::endl;
 
    return 0;
}

3. 反向遍历

#include 
#include 
 
int main() {
    std::list<int> l = {1, 2, 3, 4, 5, 6};
 
    // 反向遍历
    for (auto it = l.rbegin(); it != l.rend(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;
 
    return 0;
}

4. 其它用法

#include 
#include 
 
int main() {
    std::list<int> l = {1, 2, 3, 4, 5, 6};
 
    // 获取列表大小
    std::cout << "Size: " << l.size() << std::endl;
 
    // 检查是否为空
    if (l.empty()) {
        std::cout << "List is empty" << std::endl;
    } else {
        std::cout << "List is not empty" << std::endl;
    }
 
    // 清空列表
    l.clear();
    std::cout << "Size after clear: " << l.size() << std::endl;
 
    return 0;
}

进阶使用技巧

1. 合并和排序

#include 
#include 
 
int main() {
    std::list<int> l1 = {1, 3, 5, 7};
    std::list<int> l2 = {2, 4, 6, 8};
 
    // 合并两个已排序的列表
    l1.merge(l2);
 
    // 排序
    l1.sort();
 
    // 反转
    l1.reverse();
 
    // 输出列表 l1 的内容
    for (int n : l1) {
        std::cout << n << ' ';
    }
    std::cout << std::endl;
 
    return 0;
}

2. 去重

#include 
#include 
 
int main() {
    std::list<int> l = {1, 2, 2, 3, 3, 3, 4, 5};
 
    // 必须先排序，然后去重
    l.sort();
    l.unique();
 
    // 输出去重后的列表 l 的内容
    for (int n : l) {
        std::cout << n << ' ';
    }
    std::cout << std::endl;
 
    return 0;
}

自定义比较函数

在 `sort`、`merge` 等方法中，可以传递自定义比较函数：

#include 
#include 
 
bool customCompare(int a, int b) {
    return a > b; // 降序排列
}
 
int main() {
    std::list<int> l = {1, 3, 2, 5, 4};
 
    // 使用自定义比较函数排序
    l.sort(customCompare);
 
    // 输出排序后的列表 l 的内容
    for (int n : l) {
        std::cout << n << ' ';
    }
    std::cout << std::endl;
 
    return 0;
}

总结

`std::list` 是 C++ 标准库中功能强大且灵活的双向链表容器，适用于需要频繁插入和删除操作的场景。在我们实际开发中，根据项目的具体需求选择合适的容器，比如‘std::forward_list’等，可以显著提高代码性能和可维护性。

引用

std::list - cppreference.com