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

来自cppreference.com

 
 
 
 
void merge( forward_list& other );
(1) (C++11 起)
void merge( forward_list&& other );
(2) (C++11 起)
template < class Compare >
void merge( forward_list& other, Compare comp );
(3) (C++11 起)
template < class Compare >
void merge( forward_list&& other, Compare comp );
(4) (C++11 起)

如果 other*this 指代同一对象,那么什么也不做。

否则,将 other 合并到 *this。两个链表都应有序。不复制元素,并且在操作后容器 other 会变为空。此操作是稳定的:对于两个链表中的等价元素,来自 *this 的元素始终在来自 other 的元素之前,并且 *thisother 的等价元素顺序不更改。

迭代器和引用不会失效。指向或指代从 other 移走的元素的指针、引用和迭代器将不再涉及 other,而是会指代 *this 中的相同元素。

1,2)operator< 比较元素。
3,4)comp 比较元素。

如果 other*this 没有按对应的比较器有序,或者 get_allocator() != other.get_allocator(),那么行为未定义。

参数

other - 要交换的另一容器
comp - 比较函数对象(即满足比较 (Compare) 概念的对象),在第一参数小于(即 序于)第二参数时返回 ​true

比较函数的签名应等价于如下:

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

虽然签名不必有 const&,函数也不能修改传递给它的对象,而且必须接受(可为 const 的)类型 Type1Type2 的值,无关乎值类别(从而不允许 Type1& ,也不允许 Type1,除非 Type1 的移动等价于复制 (C++11 起))。
类型 Type1Type2 必须使得 forward_list<T,&nbsp;Allocator>::const_iterator 类型的对象能在解引用后隐式转换到这两个类型。 ​

类型要求
-
Compare 必须符合比较 (Compare) 的要求。

返回值

(无)

异常

如果因为任何原因抛出了异常,那么此函数无效果(强异常安全保证)。除非异常来自比较操作。

复杂度

如果 other*this 指代同一对象,那么不会进行比较。

否则给定 Nstd::distance(begin(), end())Rstd::distance(other.begin(), other.end())

1,2) 应用最多 N+R-1operator< 进行比较。
3,4) 应用最多 N+R-1 次比较函数 comp

示例

#include <iostream>
#include <forward_list>
 
std::ostream& operator<<(std::ostream& ostr, const std::forward_list<int>& list)
{
    for (auto &i : list)
        ostr << " " << i;
    return ostr;
}
 
int main()
{
    std::list<int> list1 = {5, 9, 1, 3, 3};
    std::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 << "合并后:" << list1 << '\n';
}

输出:

list1:1 3 3 5 9
list2:2 3 4 4 7 8
合并后:1 2 3 3 3 4 4 5 7 8 9

缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
LWG 2045 C++11 get_allocator() != other.get_allocator()
的情况下无法保证在 O(1) 时间内完成节点移动
此时行为未定义

参阅

从另一 forward_list 移动元素
(公开成员函数)
归并两个有序范围
(函数模板)
就地归并两个有序范围
(函数模板)
归并两个有序范围
(niebloid)
在原位归并两个有序范围
(niebloid)