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

  • 9316991614 2018-02-25
  • 191841613 2018-02-25
  • 16411612 2018-02-25
  • 6081981611 2018-02-25
  • 1784561610 2018-02-25
  • 4651609 2018-02-25
  • 9348111608 2018-02-25
  • 2513771607 2018-02-25
  • 6478461606 2018-02-24
  • 4985791605 2018-02-24
  • 5637141604 2018-02-24
  • 282181603 2018-02-24
  • 6217941602 2018-02-24
  • 5076141601 2018-02-24
  • 714281600 2018-02-24
  • 6607141599 2018-02-24
  • 949041598 2018-02-24
  • 6809961597 2018-02-24
  • 671871596 2018-02-24
  • 7107821595 2018-02-24