list::merge


public member function
  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, inserting all the elements of x into the list object at their respective ordered positions. This empties x and increases the list size.

The second version (template function), has the same behavior, but takes a specific function to perform the comparison operation in charge of determining the insertion points. The comparison function has to perform weak strict ordering (which basically means the comparison operation has to be transitive and irreflexive).

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 or destruction of any element object.

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)