std::forward_list merge() method

od C++11

// (1) Non const version only
void merge( forward_list& other );

// (1) Non const version only
void merge( forward_list&& other );

// (2) Non const version only
template <class Compare>
void merge( forward_list& other, Compare comp );

// (2) Non const version only
template <class Compare>
void merge( forward_list&& other, Compare comp );

Merges two sorted lists into one.

No elements are copied. The container other becomes empty after the operation.

The function does nothing if other refers to the same object as *this.
This operation is stable: for equivalent elements in the two lists, the elements from *this shall always precede the elements from other, and the order of equivalent elements of *this and other does not change.

• (1) Uses operator< to compare the elements.
• (2) Uses the given comparison function comp.

important

No iterators or references become invalidated, except that the iterators of moved elements now refer into *this, not into other.

Undefined Behavior

If get_allocator() != other.get_allocator(), the behavior is undefined.

important

The lists should be sorted into ascending order.

Parameters

• other - the container to exchange the contents with

• comp - comparison function object which returns true if the first argument is less than the second.

  The signature of the comparison function should be equivalent to the following:

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

  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 (od 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.

Return value

(none)

Complexity

At most std::distance(begin(), end()) + std::distance(other.begin(), other.end()) - 1 comparisons.

Exceptions

If an exception is thrown, this function has no effect (strong exception guarantee), except if the exception comes from the comparison function.

Example

Main.cpp

#include <iostream>
#include <forward_list>
 
std::ostream& operator<<(std::ostream& ostr, const std::forward_list<int>& list)
{
    for (const auto &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