public member function

std::list::merge

<list>
  void merge ( list<T,Allocator>& x );
template <class Compare>
  void merge ( list<T,Allocator>& x, Compare comp );
Merge sorted lists
Merges x into the list by moving all of its elements into the container at their respective ordered positions. This effectively removes all the elements in x (which becomes empty), and inserts them into the container (which expands in size by the number of elements moved).

The version with two parameters (template function), has the same behavior, but takes a specific function to perform the comparison operation in charge of determining the insertion points. This comparison function has to perform weak strict ordering (which basically means the comparison operation is required to be transitive but not reflexive).

The merging is performed using two iterators: one to iterate through x and another one to keep the insertion point in the list object; During the iteration of x, if the current element in x compares less than the element at the current insertion point in the list object, the element is removed from x and inserted into that location, otherwise the insertion point is advanced. This operation is repeated until either end is reached, in which moment the remaining elements of x (if any) are moved to the end of the list object and the function returns (this last operation is performed in constant time).

The entire operation does not involve the construction, destruction or copy of any element object. They are moved.

The pointers, references and iterators that referred to moved elements keep referring to those same elements, but iterators now iterate into the container the elements have been transferred to.

If no ordering is required, another option for merging lists is member function list::splice, which is faster.

Parameters

x
A list object containing the same type of objects as this container.
comp
Comparison function that, taking two values of the same type than those contained in the list object, returns true if the first argument is less than the second, and false otherwise.

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>
using namespace std;

// this compares equal two doubles if
//  their interger equivalents are equal
bool mycomparison (double first, double second)
{ return ( int(first)<int(second) ); }

int main ()
{
  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.push_back (2.1);

  first.merge(second,mycomparison);

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

  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 x.size() + this->size() - 1.

See also

list::splice
Move 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++