C++ STL中的forward_list::reverse()

简介

在C++中，单链表是一个非常常用的数据结构，STL中有一个轻量级的单向链表容器——forward_list。而其中一个非常有用的成员函数，就是reverse()。它可以将链表中的元素顺序全部翻转，使得原本的尾部成为了头部。

语法

void reverse() noexcept;

代码解释：

• reverse()是forward_list的成员函数，没有返回值。
• noexcept表示该函数不抛出任何可能的异常。

示例

下面，我们来演示一个例子：

#include <iostream>
#include <forward_list>

using namespace std;

int main() {
    forward_list<int> list{1, 2, 3, 4, 5};
    cout << "Original list: ";
    for (auto i = list.begin(); i != list.end(); ++i) {
        cout << *i << " ";
    }
    cout << endl;

    list.reverse();
    cout << "Reversed list: ";
    for (auto i = list.begin(); i != list.end(); ++i) {
        cout << *i << " ";
    }
    cout << endl;

    return 0;
}

输出结果：

Original list: 1 2 3 4 5 
Reversed list: 5 4 3 2 1 

我们可以看到，原本的链表中，1是头部，5是尾部，而翻转后，头部变为了5，尾部变为了1。

实现原理

forward_list是一个单向链表，没有双向指针。因此，我们不能使用通常的方法去翻转它，即通过交换节点的前后指针去实现。

所以，forward_list提供了一个成员函数reverse()，它的实现是这样的：

1. 如果链表是空的，什么也不用做。
2. 如果链表只有一个元素，也什么也不用做。
3. 如果链表中有两个或以上的元素，我们可以使用三个指针，分别指向当前节点、前一个节点和后一个节点。然后将当前节点的指针指向前一个节点，更新三个指针的位置，以完成翻转。

这个实现的时间复杂度是线性的。

注意事项

• reverse()是在原地翻转链表，会修改原本的链表。如果需要保留原链表，建议先拷贝出一份。
• 因为reverse()是一个轻量级容器，所以它不会对元素进行拷贝，即使你存储的是自定义类型。
• reverse()的时间复杂度是线性的，而不是指数级的。因此，它适用于大规模数据的操作，不会让程序变得缓慢。

结论

forward_list的reverse()函数非常有用，它可以帮助我们翻转单向链表，同时这个函数的实现也是非常高效的。如果你需要操作单向链表，不妨试试它！