C++ 容器类 <list>

C++ 标准库提供了丰富的功能，其中 <list> 是一个非常重要的容器类，用于存储元素集合，支持双向迭代器。

<list> 是 C++ 标准模板库（STL）中的一个序列容器，它允许在容器的任意位置快速插入和删除元素。与数组或向量（<vector>）不同，<list> 不需要在创建时指定大小，并且可以在任何位置添加或删除元素，而不需要重新分配内存。

语法

以下是 <list> 容器的一些基本操作：

• 包含头文件：#include <list>
• 声明列表：std::list<T> mylist;，其中 T 是存储在列表中的元素类型。
• 插入元素：mylist.push_back(value);
• 删除元素：mylist.pop_back(); 或 mylist.erase(iterator);
• 访问元素：mylist.front(); 和 mylist.back();
• 遍历列表：使用迭代器 for (auto it = mylist.begin(); it != mylist.end(); ++it)

特点

• 双向迭代：<list> 提供了双向迭代器，可以向前和向后遍历元素。
• 动态大小：与数组不同，<list> 的大小可以动态变化，不需要预先分配固定大小的内存。
• 快速插入和删除：可以在列表的任何位置快速插入或删除元素，而不需要像向量那样移动大量元素。

声明与初始化

<list> 的声明和初始化与其他容器类似：

#include <iostream>
#include <list>

int main() {
    std::list<int> lst1;                  // 空的list
    std::list<int> lst2(5);               // 包含5个默认初始化元素的list
    std::list<int> lst3(5, 10);           // 包含5个元素，每个元素为10
    std::list<int> lst4 = {1, 2, 3, 4};   // 使用初始化列表

    return 0;
}

示例：

#include <iostream>
#include <list>

int main() {
    // 创建一个整数类型的列表
    std::list<int> numbers;

    // 向列表中添加元素
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    // 访问并打印列表的第一个元素
    std::cout << "First element: " << numbers.front() << std::endl;

    // 访问并打印列表的最后一个元素
    std::cout << "Last element: " << numbers.back() << std::endl;

    // 遍历列表并打印所有元素
    std::cout << "List elements: ";
    for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 删除列表中的最后一个元素
    numbers.pop_back();

    // 再次遍历列表并打印所有元素
    std::cout << "List elements after removing the last element: ";
    for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

First element: 10
Last element: 30
List elements: 10 20 30 
List elements after removing the last element: 10 20

常用成员函数

以下是 <list> 中一些常用的成员函数：

示例

基本操作

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {10, 20, 30};

    // 插入和删除元素
    lst.push_front(5);           // 在头部插入5
    lst.push_back(40);           // 在尾部插入40
    lst.pop_front();             // 删除头部元素
    lst.pop_back();              // 删除尾部元素

    // 输出链表内容
    std::cout << "List elements: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

插入和删除特定位置的元素

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto it = lst.begin();
    std::advance(it, 2);          // 移动迭代器到第3个元素（值为3）

    lst.insert(it, 10);           // 在第3个元素前插入10
    lst.erase(it);                // 删除第3个元素

    // 输出链表内容
    std::cout << "List elements: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

排序和去重

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    lst.sort();                    // 排序
    lst.unique();                  // 删除相邻重复元素

    // 输出链表内容
    std::cout << "Sorted and unique list: ";
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

合并和反转

#include <iostream>
#include <list>

int main() {
    std::list<int> lst1 = {1, 3, 5, 7};
    std::list<int> lst2 = {2, 4, 6, 8};

    lst1.merge(lst2);              // 合并两个已排序的链表
    lst1.reverse();                // 反转链表

    // 输出链表内容
    std::cout << "Merged and reversed list: ";
    for (const auto& elem : lst1) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

与其他容器对比

C++ 容器 <forward_list>

C++ 标准库中的 <forward_list> 是一种容器，它提供了一种单向链表的数据结构。

与双向链表（std::list）不同，std::forward_list 只支持单向遍历。它适用于需要频繁进行前向遍历和插入、删除操作的场景。以下是对 std::forward_list 的详细说明：

单向链表：

• std::forward_list 是单向链表，只能从前往后遍历，不能反向遍历。
• 由于其单向链表的结构，插入和删除操作在已知位置的情况下非常高效（O(1) 复杂度）。

低内存开销：

• 与 std::list 相比，std::forward_list 只需要一个指向下一个节点的指针，节省了内存。

不支持随机访问：

• 不支持通过索引访问元素，不能使用 operator[] 或 at 方法，只能通过迭代器进行访问。

语法

std::forward_list 是 C++ 标准库中的一个模板类，定义在 <forward_list> 头文件中。它使用模板参数 T 来指定存储在列表中的元素类型。

以下是 std::forward_list 的基本语法：

#include <forward_list>

std::forward_list<T> list;

构造函数

std::forward_list 提供了多种构造函数，包括：

• 默认构造函数：创建一个空的 forward_list。
• 带初始值的构造函数：创建一个包含给定初始值的 forward_list。
• 带范围的构造函数：创建一个包含指定范围内元素的 forward_list。

常用成员函数

• void push_front(const T& value)：在列表的前端插入一个元素。
• void pop_front()：移除列表前端的元素。
• iterator before_begin()：返回指向列表前端之前的迭代器。
• iterator begin()：返回指向列表前端的迭代器。
• iterator end()：返回指向列表末尾的迭代器。

实例

下面是一个使用 std::forward_list 的简单示例，包括创建列表、添加元素、遍历列表和输出结果。

#include <iostream>
#include <forward_list>

int main() {
    // 创建一个空的 forward_list
    std::forward_list<int> fl;

    // 在列表前端添加元素
    fl.push_front(10);
    fl.push_front(20);
    fl.push_front(30);

    // 遍历 forward_list 并输出元素
    for (auto it = fl.begin(); it != fl.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 输出结果：30 20 10

    return 0;
}

当你运行上述代码时，你将看到以下输出：

30 20 10

std::forward_list 是 C++ 标准库中一个非常有用的容器，特别适合于需要在列表前端进行频繁插入和删除操作的场景。虽然它不支持随机访问，但在某些情况下，它的性能优势可以弥补这一不足。希望这篇文章能帮助初学者更好地理解和使用 std::forward_list。