Namespaces
Variants

std::forward_list<T,Allocator>:: merge

From cppreference.net

C++
Containers library
std::forward_list
Member functions
Non-member functions
(until C++20) (until C++20) (until C++20) (until C++20) (until C++20)
Deduction guides (C++17)
void merge ( forward_list & other ) ;
(1) (自 C++11 起)
(自 C++26 起为 constexpr)
void merge ( forward_list && other ) ;
(2) (自 C++11 起)
(自 C++26 起为 constexpr)
template < class Compare >
void merge ( forward_list & other, Compare comp ) ;
(3) (自 C++11 起)
(自 C++26 起为 constexpr)
template < class Compare >
void merge ( forward_list && other, Compare comp ) ;
(4) (自 C++11 起)
(自 C++26 起为 constexpr)

将两个已排序列表合并为一个有序列表。

  • 如果 other 指向与 * this 相同的对象，则不执行任何操作。
  • 否则，将 other 中的所有元素转移到 * this 。合并后 other 将为空。

此操作是稳定的：

  • 对于两个列表中相等的元素，来自 * this 的元素始终位于来自 other 的元素之前。
  • * this 和 other 中相等元素的顺序不会改变。
1,2) 等价于 merge ( other, std:: less < T > ( ) ) (C++14 前) merge ( other, std:: less <> ( ) ) (C++14 起) 。
3,4) 使用 comp 对元素进行比较。
若满足以下任意条件，则行为未定义：
  • * this 或 other 未相对于比较器 comp 有序 。
  • get_allocator ( ) == other. get_allocator ( ) 为 false 。

不会使任何迭代器或引用失效。指向从 * this 移动的元素的指针和引用，以及指向这些元素的迭代器，将引用 * this 中的相同元素，而非 other 。

目录

参数

other - 待合并的另一容器
comp - 比较函数对象（即满足 Compare 要求的对象），当第一个参数 小于 （即排序在 之前 ）第二个参数时返回​ true 。

比较函数的签名应等价于如下形式：

bool cmp ( const Type1 & a, const Type2 & b ) ;

虽然签名不需要包含 const & ，但函数不得修改传递给它的对象，且必须能够接受所有（可能为const的） Type1 与 Type2 类型的值，无论其 值类别 为何（因此不允许 Type1& ，也不允许 Type1 ，除非对于 Type1 类型移动等价于复制 (C++11 起) ）。
类型 Type1 与 Type2 必须使得 forward_list < T, Allocator > :: const_iterator 类型的对象在解引用后能隐式转换到这两个类型。 ​

类型要求
-
Compare 必须满足 Compare 的要求。

异常

若因任何原因抛出异常，这些函数将不产生任何效果（ 强异常安全保证 ）。除非异常源自比较操作。

复杂度

如果 other 与 * this 指向同一对象，则不执行任何比较操作。

否则，给定 N 1 为 std:: distance ( begin ( ) , end ( ) ) 且 N 2 为 std:: distance ( other. begin ( ) , other. end ( ) ) ：

1,2) 最多进行 N 1 +N 2 -1 次比较，使用 operator < 。
3,4) 最多需要 N 1 +N 2 -1 次比较函数 comp 的调用。

示例

运行此代码 
#include <iostream>
#include <forward_list>
std::ostream& operator<<(std::ostream& ostr, const std::forward_list<int>& list)
{
    for (const int i : list)
        ostr << ' ' << i;
    return ostr;
}
int main()
{
    std::forward_list<int> list1 = {5, 9, 1, 3, 3};
    std::forward_list<int> list2 = {8, 7, 2, 3, 4, 4};
    list1.sort();
    list2.sort();
    std::cout << "list1: " << list1 << '\n';
    std::cout << "list2: " << list2 << '\n';
    list1.merge(list2);
    std::cout << "merged:" << list1 << '\n';
}

输出： 

list1:  1 3 3 5 9
list2:  2 3 4 4 7 8
merged: 1 2 3 3 3 4 4 5 7 8 9

缺陷报告

以下行为变更缺陷报告被追溯应用于先前发布的C++标准。

缺陷报告 应用于 发布时行为 正确行为
LWG 2045 C++11 当
get_allocator ( ) ! = other. get_allocator ( )
时无法保证O(1)节点移动 		此情况下
行为未定义
LWG 3088 C++11 当 * this 与 other
引用同一对象时效果未定义
operator < 对指针元素可能行为异常 		规定为无操作
实现定义
使用严格全序

参见

从另一个 forward_list 转移元素
(公开成员函数)
合并两个已排序范围
(函数模板)
原地合并两个有序范围
(函数模板)
(C++20)
合并两个已排序范围
(算法函数对象)
(C++20)
原地合并两个有序范围
(算法函数对象)