C++ STL中的forward_list merge()

在C++ STL的forward_list中，有一个非常有用的函数叫做merge()。这个函数可以将两个已排序的链表合并成一个。这个函数非常简单易用，但是却非常实用。

下面我们来看一下merge()函数的定义：

void merge( forward_list& other );

其中，参数other就是需要合并到当前链表中的另一个链表。

函数的作用是将两个链表合并为一个有序的链表。在merge()之前，两个链表都必须是已排序的。

下面是一个使用例子：

#include <iostream>
#include <forward_list>

int main()
{
    std::forward_list<int> first = { 1, 3, 5 };
    std::forward_list<int> second = { 2, 4, 6 };

    first.merge(second);

    for (auto i : first) std::cout << i << ' ';
    std::cout << '\n';
}

这段代码中，我们首先定义了两个已排序的链表first和second，然后调用了first的merge()函数，将second链表合并进来。

最后我们遍历打印了first链表，可以看到，链表已经按照从小到大的顺序排好了。

输出结果为：

1 2 3 4 5 6

注意，合并的两个链表在merge()函数结束后，second链表会被清空，因为被合并进来的元素都已经被移动到了first链表中。如果要保留second链表，可以将merge()的参数改为second的副本。

first.merge(second);  // 清空second链表

std::forward_list<int> second_copy = second;  // 保存second的副本
first.merge(second_copy);

除了将已排序的链表合并外，merge()函数还可以接受一个可调用对象作为第二个参数，用于指定自定义的比较函数。

#include <iostream>
#include <forward_list>
#include <cstdio>

bool compare(int a, int b)
{
    return a > b;
}

int main()
{
    std::forward_list<int> first = { 1, 3, 5 };
    std::forward_list<int> second = { 2, 4, 6 };

    first.merge(second, compare);

    for (auto i : first) std::cout << i << ' ';
    std::cout << '\n';
}

这段代码中，compare()函数返回true和false的规则与之前的例子正好相反。所以，我们使用compare()函数作为merge()的第二个参数，即可得到从大到小的有序链表。

输出结果为：

6 5 4 3 2 1

可以看到，链表已经按照从大到小的顺序排好了。

结论

merge()是forward_list的一个非常实用的函数，可以将两个已排序的链表快速合并成一个有序链表。我们只需要调用merge()函数即可，非常方便。同时，通过传递一个自定义的比较函数，我们还可以得到不同的排序结果。在使用forward_list时，不妨尝试使用merge()来简化自己的代码。