public member function
<list>

std::list::merge

(1)
  void merge (list& x);
(2)
template <class Compare>
  void merge (list& x, Compare comp);
(1)
  void merge (list& x);
  void merge (list&& x);
(2)
template <class Compare>
  void merge (list& x, Compare comp);
template <class Compare>
  void merge (list&& x, Compare comp);
Merge sorted lists
Merges x into the 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 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).

The function does nothing if (&x == this).

Parameters

x
A list object of the same type (i.e., with the same template parameters, T and Alloc).
Note that this function modifies x 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 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
31
32
33
34
35
36
37
38
 
// list::merge
#include <iostream>
#include <list>

// compare only integral part:
bool mycomparison (double first, double second)
{ return ( int(first)<int(second) ); }

int main ()
{
  std::list<double> first, second;

  first.push_back (3.1);
  first.push_back (2.2);
  first.push_back (2.9);

  second.push_back (3.7);
  second.push_back (7.1);
  second.push_back (1.4);

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

  first.merge(second);

  // (second is now empty)

  second.push_back (2.1);

  first.merge(second,mycomparison);

  std::cout << "first contains:";
  for (std::list<double>::iterator it=first.begin(); it!=first.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}


Output:
first contains: 1.4 2.2 2.9 2.1 3.1 3.7 7.1
Notice how in the second merger, the function mycomparison (which only compares the integral parts) did not consider 2.1 lower than 2.2 or 2.9, so it was inserted right after them, before 3.1.


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 x 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

list::splice
Transfer elements from list to list (public member function )
list::insert
Insert elements (public member function )
list::remove
Remove elements with specific value (public member function )
list::erase
Erase elements (public member function )
list::push_back
Add element at the end (public member function )

C++