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

STL（Standard Template Library）是C++提供的标准库之一，它提供了一系列的模板类和函数，进一步支持了C++的泛型编程。其中，forward_list是STL中的一个容器，它类似于单向链表，其 swap() 函数可以用于两个 forward_list 容器之间的内容交换。

forward_list 介绍

std::forward_list 是一个单向链表容器，它只能从前往后遍历，无法像双向链表那样反向遍历。与 vector 和 deque 容器不同，forward_list 容器没有提供随机访问元素的方法，也就是说，只能访问第一个元素，必须从头开始遍历，所以才会叫做单向链表。

使用 forward_list 前需要包含头文件：

#include <forward_list>

创建和初始化 forward_list：

std::forward_list<int> flist = {1, 3, 5, 7, 9};

向 forward_list 中添加元素：

flist.push_front(0);   // 在前面添加
flist.insert_after(flist.begin(), 2);   // 在指定位置后添加

遍历 forward_list：

for (auto x : flist) {
    std::cout << x << " ";
}
// 输出结果为：0 1 2 3 5 7 9

forward_list::swap() 函数

swap() 是 forward_list 类中提供的成员函数之一，它用于交换两个 forward_list 的元素。具体用法如下：

void swap (forward_list& fwd);

其中，fwd 参数是另一个 forward_list 容器的引用。调用 swap() 函数将当前 forward_list 和 fwd 的元素进行交换。

例如：

std::forward_list<int> flist1 = {1,3,5};
std::forward_list<int> flist2 = {2,4,6};

flist1.swap(flist2);

std::cout << "flist1: ";
for (auto x : flist1) {
    std::cout << x << " ";
}
std::cout << std::endl;

std::cout << "flist2: ";
for (auto x : flist2) {
    std::cout << x << " ";
}

输出结果为：

flist1: 2 4 6
flist2: 1 3 5

forward_list::swap() 的使用场景

forward_list::swap() 函数可以用于将两个 forward_list 容器的内容进行交换，这在某些场景下非常有用。例如，当需要对两个链表进行排序时，可以通过 swap() 将两个链表的内容互换，然后对每个链表单独进行排序操作，再通过 swap() 函数将链表的内容互换回来，最终得到排序后的链表。

下面是一个使用 forward_list::swap() 函数实现链表排序的示例代码：

std::forward_list<int> sort_flist(std::forward_list<int> flist) {
    if (flist.empty() || std::next(flist.begin()) == flist.end()) {
        return flist;
    }
    std::forward_list<int> left;
    std::forward_list<int> right;
    while (!flist.empty()) {
        left.push_front(flist.front());
        flist.pop_front();
        if (!flist.empty()) {
            right.push_front(flist.front());
            flist.pop_front();
        }
    }
    left = sort_flist(left);
    right = sort_flist(right);
    left.reverse();
    right.reverse();
    left.swap(right);
    std::forward_list<int> result(std::move(left));
    result.merge(std::move(right));
    return result;
}

该函数接受一个 forward_list 容器为参数，返回一个排好序的 forward_list 容器。函数内部先判断传入的链表是否为空或者只有一个节点。如果是，则直接返回原链表。如果链表不为空，则将链表拆成两个链表，分别进行递归排序，并将两个排序完成的链表进行合并。

其中，关键步骤是在排序完成后，将 left 与 right 进行交换，使得原来是从小到大排序的 left 变成从大到小排序，原来是从大到小排序的 right 变成从小到大排序。这样就可以直接将两个链表拼接在一起了。

最后，将拼接好的链表返回即可。