C++中 Forward List 和 List 的区别

在C++中，STL库提供了多种容器类型来存储和操作元素，其中最常见的就是List和Forward List。虽然这两种容器都可以用于存储元素，但它们的实现和使用方式有着很大的区别。在本文中，我们将详细研究这两种容器，并比较它们之间的不同之处。

List

List是一种双向链表容器，它允许高效地在任意位置插入和删除元素。由于在插入和删除元素时不需要移动大量的内存块，因此List比vector更适合于频繁的插入和删除操作。

下面是一个创建List并使用它的示例代码：

#include <iostream>
#include <list>
using namespace std;

int main()
{
    // 创建一个List并插入元素
    list<int> myList;
    myList.push_back(1);
    myList.push_back(2);
    myList.push_back(3);

    // 遍历List并输出每个元素
    for (list<int>::iterator it=myList.begin(); it!=myList.end(); ++it)
        cout << *it << " ";
    cout << endl;

    // 在List的中间插入一个元素
    list<int>::iterator it=myList.begin();
    ++it; // it指向第一个元素之后的位置
    myList.insert(it, 4);

    // 遍历List并输出每个元素
    for (list<int>::iterator it=myList.begin(); it!=myList.end(); ++it)
        cout << *it << " ";
    cout << endl;

    // 删除List中的第二个元素
    it = myList.begin();
    ++it; // it指向第一个元素之后的位置
    myList.erase(it);

    // 遍历List并输出每个元素
    for (list<int>::iterator it=myList.begin(); it!=myList.end(); ++it)
        cout << *it << " ";
    cout << endl;

    return 0;
}

这段代码创建了一个List并向其中插入三个元素，然后在第二个元素后插入一个新元素，最后删除了第二个元素。程序输出结果如下：

1 2 3
1 4 2 3
1 4 3

Forward List

和List一样，Forward List也是一种链表容器，但它只能单向遍历链表。由于它没有双向链表中的prev指针，因此删除和插入某些元素时需要更多的操作。因为没有prev指针，所以在进行删除和插入操作时必须先找到要操作元素的前一个元素，这意味着它的效率比List差一些。不过，它的优点是它比List更紧凑，因为它不需要为每个元素存储额外的指针。

下面是一个创建Forward List并使用它的示例代码：

#include <iostream>
#include <forward_list>
using namespace std;

int main()
{
    // 创建一个Forward List并插入元素
    forward_list<int> myList;
    myList.push_front(1);
    myList.push_front(2);
    myList.push_front(3);

    // 遍历Forward List并输出每个元素
    for (int& x : myList)
        cout << x << " ";
    cout << endl;

    // 在Forward List的中间插入一个元素
    forward_list<int>::iterator it=myList.begin();
    ++it; // it指向第一个元素之后的位置
    myList.insert_after(it, 4);

    // 遍历Forward List并输出每个元素
    for (int& x : myList)
        cout << x << " ";
    cout << endl;

    // 删除Forward List中的第二个元素
    it = myList.begin();
    ++it; // it指向第一个元素之后的位置
    myList.erase_after(it);

    //遍历Forward List并输出每个元素
    for (int& x : myList)
        cout << x << " ";
    cout << endl;

    return 0;
}

这段代码创建了一个Forward List并向其中插入了三个元素，然后在第二个元素后插入一个新元素，最后删除了第二个元素。程序输出结果如下：

3 2 1
3 4 2 1
3 4 1

区别

这两种容器的主要区别在于它们内部的实现和支持的操作。List是一个双向链表，支持双向迭代器和随机访问。由于它可以直接访问任意元素，因此在大多数场景中它更加快速。但是，由于它需要为每个元素存储额外的指针，因此它的存储空间比Forward List更大。

Forward List是一个单向链表，支持单向迭代器和顺序访问。由于它没有prev指针，因此许多操作需要更多的步骤才能完成，这意味着它可能比List慢一些。但是，由于它存储的元素比List紧凑，因此对于大量元素的场景来说，它可能更加高效。

另一个不同之处是它们支持的操作不同。List支持从任意位置插入和删除元素，而Forward List则不支持在中间插入元素。此外，List支持逆向遍历，而Forward List只能单向遍历。如果你的应用程序需要在中间插入元素或逆向遍历容器中的元素，那么List可能更适合你。如果你的应用程序只需要单向遍历容器中的元素，并且需要更紧凑的存储，那么Forward List可能更合适。