C++中 Forward List 和 List 的区别

Forward List 是一种序列容器，允许单向顺序访问其数据。它包含相同类型的数据。在 STL 中，它使用单向链表实现，插入和删除需要常数时间。此时，forward list 中的元素在内存中是分散的，通过将列表的每个元素与下一个元素链接来维护排序。因此，它可以高效利用内存。从 C++11 开始引入。

Forward List 的实现:

// CPP程序演示前向列表
#include <bits/stdc++.h>
using namespace std;
 
// Driver Code
int main()
{
    // 声明前向列表
    forward_list<int> flist1;
 
    // 使用 assign() 分配值
    flist1.assign({ 10, 12, 13, 15 });
 
    // 显示前向列表
    cout << "前向列表的元素是：";
    for (auto a : flist1)
        cout << a << " ";
    return 0;
}

输出：

前向列表的元素是：10 12 13 15

List 也是一种序列容器，允许双向顺序访问其数据。它包含相同类型的数据。在 STL 中，它使用双向链表实现，插入和删除需要常数时间。它允许非连续的内存分配。列表的每个元素都有一个链接，指向其后面和前面的元素。由于其常数插入和删除时间和双向顺序访问，List 在排序算法中被广泛使用。

List 的实现:

// CPP程序演示列表
#include <bits/stdc++.h>
using namespace std;
 
// Driver Code
int main()
{
    // 声明一个列表
    list<int> list1;
 
    // 使用 assign() 分配值
    list1.assign({ 1, 2, 10, 15 });
 
    // 显示列表
    cout << "列表的元素是：";
    for (auto a : list1)
        cout << a << " ";
    return 0;
}

输出：

列表的元素是：1 2 10 15

Forward List 和 List 的区别

Forward List	List
使用单向链表实现	使用双向链表实现
占用的内存相对较少	占用的内存相对较多
插入和删除元素的开销较小，因为每个节点的指针较少，因此性能更好。	插入和删除元素的开销较大，因为每个节点的指针较多，因此性能较差。
仅支持单向顺序访问	支持双向顺序访问和反向访问
比 List 更高效	比 Forward List 更低效
通常用于需要单向顺序访问的场合，如实现二叉树、哈希表、栈等。	通常用于需要双向顺序访问的场合，如哈希中的链式法、图的邻接表表示等。