public member function
<forward_list>

std::forward_list::merge

(1)
  void merge (forward_list& fwdlst);
  void merge (forward_list&& fwdlst);
(2)
template <class Compare>
  void merge (forward_list& fwdlst, Compare comp);
template <class Compare>
  void merge (forward_list&& fwdlst, Compare comp);
Merge sorted lists
Merges x into the forward_list by transferring all of its elements at their respective ordered positions into the container (both containers shall already be ordered).

This effectively removes all the elements in x (which becomes empty), and inserts them into their ordered position within container (which expands in size by the number of elements transferred). The operation is performed without constructing nor destroying any element: they are transferred, no matter whether x is an lvalue or an rvalue, or whether the value_type supports move-construction or not.

The template versions with two parameters (2), have the same behavior, but take a specific predicate (comp) to perform the comparison operation between elements. This comparison shall produce a strict weak ordering of the elements (i.e., a consistent transitive comparison, without considering its reflexiveness).

This function requires that the forward_list containers have their elements already ordered by value (or by comp) before the call. For an alternative on unordered lists, see list::splice.

Assuming such ordering, each element of x is inserted at the position that corresponds to its value according to the strict weak ordering defined by operator< or comp. The resulting order of equivalent elements is stable (i.e., equivalent elements preserve the relative order they had before the call, and existing elements precede those equivalent inserted from x).

Parameters

fwdlst
A forward_list object of the same type (i.e., with the same template parameters, T and Alloc) and using an identical allocator.
Note that this function modifies fwdlst no matter whether an lvalue or rvalue reference is passed.
comp
Binary predicate that, taking two values of the same type than those contained in the forward_list, returns true if the first argument is considered to go before the second in the strict weak ordering it defines, and false otherwise.
This shall be a function pointer or a function object.

Return value

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
// forward_list::merge
#include <iostream>
#include <forward_list>
#include <functional>

int main ()
{
  std::forward_list<double> first = {4.2, 2.9, 3.1};
  std::forward_list<double> second = {1.4, 7.7, 3.1};
  std::forward_list<double> third = {6.2, 3.7, 7.1};

  first.sort();
  second.sort();
  first.merge(second);

  std::cout << "first contains:";
  for (double& x: first) std::cout << " " << x;
  std::cout << std::endl;

  first.sort (std::greater<double>());
  third.sort (std::greater<double>());
  first.merge (third, std::greater<double>());

  std::cout << "first contains:";
  for (double& x: first) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}


Output:
first contains: 1.4 2.9 3.1 3.1 4.2 7.7
first contains: 7.7 7.1 6.2 4.2 3.7 3.1 3.1 2.9 1.4

Complexity

At most, linear in the sum of both container sizes minus one (comparisons).

Iterator validity

No changes on the iterators, pointers and references related to the container before the call.
The iterators, pointers and references that referred to transferred elements keep referring to those same elements, but iterators now iterate into the container the elements have been transferred to.

Data races

Both the container and fwdlst are modified.
Concurrently accessing or modifying their elements is safe, although iterating through either container is not.

Exception safety

If the allocators in both containers do not compare equal, if comp does not define a strict weak ordering, or if the container elements are not ordered according to it, it causes undefined behavior.
Otherwise, if an exception is thrown by a comparison, the container is left in a valid state (basic guarantee).
Otherwise, if an exception is thrown, there are no changes in the container (strong guarantee).

See also

forward_list::splice_after
Transfer elements from another forward_list (public member function )
forward_list::insert_after
Insert elements (public member function )
forward_list::remove
Remove elements with specific value (public member function )
forward_list::erase_after
Erase elements (public member function )
forward_list::push_front
Insert element at beginning (public member function )

C++