C++ 单向列表

C++ forward lists 是序列容器，按照严格的线性序列排序，您可以在常数时间内在序列的任何位置添加或删除元素。

forward list 中的元素存储了其下一个元素位置的信息。因此，与 array、vector 等容器相比，它们在插入、移动和提取元素方面效率更高。

但是，forward list 不支持直接随机访问。

创建 Forward List

要创建 forward list，我们必须在代码中包含 <forward_list> 头文件。

#include <forward_list>

我们可以将 forward list 初始化为

std::forward_list<data_type> forward_list_name = {value1, value2, value3, ...};

这里，

• data_type - forward list 中的数据类型。
• forward_list_name - forward list 的名称。
• value1, value2, value3, ... - 要插入的值。

例如，

// create an integer forward list
std::forward_list<int> integer_fwd_list = {1, 3, 2, 4, 5};

// create a string forward list
std::forward_list<string> string_fwd_list = {"Eeny", "Meeny", "Miny", "Moe"};

示例 1：C++ Forward List

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

int main() {

    forward_list<int> fwd_list = {1, 3, 2, 4, 5};

    // print the elements in the forward list
    for (const int& element : fwd_list) {
        cout << element << " ";
    }

    return 0;
}

输出

1 3 2 4 5 

请注意，元素出现的顺序与它们插入的顺序相同。

注意：在本教程中，我们将使用 std 命名空间。因此，我们在示例中省略了 std::。

Forward Lists Methods

以下是一些常用的 forward lists 方法

示例 2：查找 Forward List 的第一个元素

我们可以使用 front() 函数访问 forward list 的第一个元素。例如，

#include <forward_list>
#include <iostream>

using namespace std;

int main() {

    forward_list<int> fwd_list = {1, 2, 3, 4, 5};

    // access the first element
    int first_element = fwd_list.front();

    cout << "The first element is: " << first_element;

    return 0;
}

输出

The first element is: 1

示例 3：向 Forward List 添加元素

我们可以通过两种方式向 forward list 添加元素

• push_front() - 在列表开头添加一个元素。
• insert_after() - 在指定位置添加一个元素。

例如，

#include <forward_list>
#include <iostream>

using namespace std;

int main() {

    forward_list<int> fwd_list = {1, 2, 5};

    // add an element to the front
    fwd_list.push_front(2);

    cout << "Forward List after push_front(): ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    cout << endl;

    // point iterator to the 2nd position of the forward list
    auto itr = fwd_list.begin();
    advance(itr, 1);

    // insert element 7 at the 3rd position
    fwd_list.insert_after(itr, 7);

    cout << "Forward List after insert_after(): ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

输出

Forward List after push_front(): 2 1 2 5 
Forward List after insert_after(): 2 1 7 2 5  

在这里，fwd_list.push_front(); 将 2 添加到 fwd_list 的开头。

但是，要将 7 插入到第三个位置，我们必须首先将 itr 迭代器定位到 forward list 的第二个位置

// point itr to the second position
auto itr = fwd_list.begin();
advance(itr, 1);

然后，我们将元素插入到 itr 指向位置的后面

// insert 7 one position after itr
fwd_list.insert_after(itr, 7); 

示例 4：更新 Forward List 的内容

我们可以使用 assign() 函数用新元素更新 forward list 的全部内容。例如，

#include <forward_list>
#include <iostream>

using namespace std;

int main() {

    forward_list<int> fwd_list = {1, 2, 5};
    
    cout << "Forward List before assign(): ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    
    // replace the entire content of the forward list
    // with new elements 3 and 4
    fwd_list.assign({3, 4});

    cout << "\nForward List after assign(): ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    cout << endl;
    
    return 0;    
}

输出

Forward List before assign(): 1 2 5 
Forward List after assign(): 3 4 

正如您所见，assign() 函数会用新内容替换 forward list 的原始内容。

示例 5：从 Forward List 中删除元素

我们可以通过三种方式从 forward list 中删除元素

• pop_front() - 删除列表的第一个元素。
• remove() - 从列表中删除指定元素的所有出现。
• clear() - 删除列表中的所有元素。

例如，

#include <forward_list>
#include <iostream>

using namespace std;

int main() {

    forward_list<int> fwd_list = {1, 2, 3, 4, 3, 5};

    cout << "Original Forward List: ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    cout << endl;

    // remove the first element
    fwd_list.pop_front();

    cout << "Forward List after pop_front(): ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    cout << endl;

    // remove all occurrences of 3
    fwd_list.remove(3);

    cout << "Forward List after remove(3): ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    cout << endl;

    // remove all elements of the list
    fwd_list.clear();

    cout << "Forward List after clear(): ";
    for (const int& element : fwd_list) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

输出

Original Forward List: 1 2 3 4 3 5 
Forward List after pop_front(): 2 3 4 3 5 
Forward List after remove(3): 2 4 5 
Forward List after clear():