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

For equivalent elements in the two lists, the elements from *this always precede the elements from other.
The order of equivalent elements of *this and other does not change.

1,2) Equivalent to merge(other, std::less <T>())(until C++14)merge(other, std::less <>())(since C++14).

3,4) Elements are compared using comp.

If any of the following conditions is satisfied, the behavior is undefined:

*this or other is not sorted with respect to the comparator comp.
get_allocator() == other.get_allocator() is false.

No iterators or references become invalidated. The pointers and references to the elements moved from *this, as well as the iterators referring to these elements, will refer to the same elements of *this, instead of other.

While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1& is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy(since C++11)).
The types Type1 and Type2 must be such that an object of type forward_list<T, Allocator>::const_iterator can be dereferenced and then implicitly converted to both of them.

Type requirements

-Compare must meet the requirements of Compare.

[edit] Exceptions

If an exception is thrown for any reason, these functions have no effect (strong exception safety guarantee). Except if the exception comes from a comparison.

[edit] Complexity

If other refers to the same object as *this, no comparisons are performed.

Otherwise, given \(\scriptsize N_1\)N1 as std::distance (begin(), end()) and \(\scriptsize N_2\)N2 as std::distance (other.begin(), other.end()):

1,2) At most \(\scriptsize N_1 + N_2 - 1\)N1+N2-1 comparisons using operator<.

3,4) At most \(\scriptsize N_1 + N_2 - 1\)N1+N2-1 applications of the comparison function comp.

[edit] Example

Run this code

#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';
}

Output:

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

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 2045	C++11	O(1) node moving could not be guaranteed if get_allocator() != other.get_allocator()	the behavior is undefined in this case
LWG 3088	C++11	the effect when *this and other refer to the same object was not specified operator< could misbehave for pointer elements	specified as no-op implementation-defined strict total order used