C++ STL list

在 C++ 标准模板库（STL）中，std::list 是一个双向链表容器，提供了高效的插入和删除操作，特别适合需要频繁修改元素顺序的场景。下面将详细介绍 std::list 的特性、常用成员函数以及使用示例。

1. std::list 的特性

• 双向链表：每个元素都有指向前一个和后一个元素的指针，支持双向遍历。
• 动态大小：可以根据需要动态增加或减少元素数量，无需预先分配内存。
• 任意位置插入和删除效率高：在已知位置的情况下，插入和删除操作的时间复杂度为 O(1)。
• 不支持随机访问：无法像 std::vector 那样通过索引直接访问元素，必须通过迭代器顺序访问。

2. 包含头文件

使用 std::list 需要包含 <list> 头文件：

#include <list>

3. 声明和初始化 std::list

#include <list>
#include <iostream>

int main() {
    // 声明一个空的整数列表
    std::list<int> myList;

    // 使用初始化列表声明并初始化列表
    std::list<int> anotherList = {1, 2, 3, 4, 5};

    // 声明一个具有固定大小的列表，并初始化所有元素为10
    std::list<int> sizedList(10, 10);

    // 使用另一个列表的元素初始化
    std::list<int> copiedList(anotherList);

    return 0;
}

4. 常用成员函数

4.1 元素访问

• front()：访问第一个元素。
• back()：访问最后一个元素。

std::list<int> lst = {1, 2, 3};
std::cout << "第一个元素: " << lst.front() << std::endl; // 输出 1
std::cout << "最后一个元素: " << lst.back() << std::endl; // 输出 3

4.2 容量

• empty()：检查列表是否为空。
• size()：返回列表中的元素数量。

if (lst.empty()) {
    std::cout << "列表为空。" << std::endl;
} else {
    std::cout << "列表大小: " << lst.size() << std::endl; // 输出 3
}

4.3 修改容器

• push_back(value)：在列表末尾添加元素。
• push_front(value)：在列表开头添加元素。
• pop_back()：移除列表末尾的元素。
• pop_front()：移除列表开头的元素。
• insert(iterator position, value)：在指定位置插入元素。
• erase(iterator position)：移除指定位置的元素。
• clear()：移除所有元素。

lst.push_back(4);
lst.push_front(0);
// lst 现在为 {0, 1, 2, 3, 4}

lst.pop_back(); // 移除4
lst.pop_front(); // 移除0
// lst 现在为 {1, 2, 3}

auto it = lst.begin();
++it; // 指向2
lst.insert(it, 10); // 在2之前插入10
// lst 现在为 {1, 10, 2, 3}

it = lst.begin();
++it; ++it; // 指向2
lst.erase(it); // 移除2
// lst 现在为 {1, 10, 3}

lst.clear(); // lst 现在为空

4.4 迭代器

std::list 支持双向迭代器，可以用于遍历列表中的元素。

for (auto it = lst.begin(); it != lst.end(); ++it) {
    std::cout << *it << " ";
}

// 使用范围-based for 循环（需要 C++11 及以上）
for (const auto& element : lst) {
    std::cout << element << " ";
}

4.5 其他常用函数

• splice()：将一个列表的元素转移到另一个列表。
• remove(value)：移除所有等于指定值的元素。
• remove_if(predicate)：移除满足条件的元素。
• sort()：对列表进行排序。
• reverse()：反转列表中的元素顺序。

std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};

// 将 list2 的所有元素转移到 list1 的末尾
list1.splice(list1.end(), list2);
// list1 现在为 {1, 2, 3, 4, 5, 6}

// 移除所有值为3的元素
list1.remove(3);
// list1 现在为 {1, 2, 4, 5, 6}

// 排序列表
list1.sort();
// list1 保持 {1, 2, 4, 5, 6}（已经有序）

// 反转列表
list1.reverse();
// list1 现在为 {6, 5, 4, 2, 1}

5. 使用示例

下面是一个综合示例，展示如何使用 std::list 进行基本操作：

#include <iostream>
#include <list>

int main() {
    // 创建并初始化列表
    std::list<int> numbers = {5, 3, 1, 4, 2};

    // 输出初始列表
    std::cout << "初始列表: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 在开头插入元素
    numbers.push_front(0);
    std::cout << "插入0后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 在末尾插入元素
    numbers.push_back(6);
    std::cout << "插入6后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除第一个元素
    numbers.pop_front();
    std::cout << "删除第一个元素后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除最后一个元素
    numbers.pop_back();
    std::cout << "删除最后一个元素后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 在指定位置插入元素
    auto it = numbers.begin();
    std::advance(it, 2); // 指向第三个元素（1）
    numbers.insert(it, 99);
    std::cout << "在第三个位置插入99后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 移除特定值的元素
    numbers.remove(4);
    std::cout << "移除所有4后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 排序列表
    numbers.sort();
    std::cout << "排序后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 反转列表
    numbers.reverse();
    std::cout << "反转后: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

6. 注意事项

• 不支持随机访问：与 std::vector 和 std::deque 不同，std::list 不支持通过索引直接访问元素，必须通过迭代器进行遍历。
• 内存开销：由于每个元素都有前后指针，std::list 的内存开销比 std::vector 大。
• 迭代器失效：在插入或删除元素时，只有被删除元素对应的迭代器会失效，其他迭代器仍然有效（除非操作导致列表重新分配，但 std::list 不会重新分配内存）。

7. 与其他容器的比较

根据具体需求选择合适的容器。例如，如果需要频繁在中间插入或删除元素，且不需要随机访问，std::list 是一个不错的选择；如果需要快速的随机访问，且主要在尾部进行插入和删除，std::vector 更为合适。

总结

std::list 是 C++ STL 中一个功能强大的双向链表容器，适用于需要频繁修改元素顺序的场景。了解其特性和常用成员函数，可以帮助我们更高效地编写代码。在实际应用中，应该根据具体需求选择最合适的容器类型。