C++ <list> - merge() Function

The C++ list::merge function is used to merge two sorted lists into one. The lists should be sorted into ascending order before calling this function.

The function merges the list other into the given list by transferring all of its elements at their respective ordered positions into the list. The container other becomes empty after the operation, and the whole operation is performed without constructing or destroying any element.

The elements of two lists are compared using operator< (in first version) or comp (in second version).

//version 1
void merge (list& other);
 
//version 2
template <class Compare>
  void merge (list& other, Compare comp);

//version 1
void merge (list& other);
void merge (list&& other);

//version 2
template <class Compare>
  void merge (list& other, Compare comp);
template <class Compare>
  void merge (list&& other, Compare comp);

Parameters

`other`	Specify another list object of same type to merge.
`comp`	Specify a binary function that accepts two element as arguments, and returns a value convertible to bool. The returned value indicates whether the first argument is considered to go before the second using the strict weak ordering it defines.

Return Value

None.

Time Complexity

Linear i.e, Θ(n).

Example:

In the example below, the list::merge function is used to merge two sorted lists.

#include <iostream>
#include <list>
using namespace std;
 
int main (){
  list<int> list1{10, 20, 50, 60};
  list<int> list2{10, 30, 45, 75};
  list<int>::iterator it;

  cout<<"list1 contains: ";
  for(it = list1.begin(); it != list1.end(); it++)
    cout<<*it<<" ";

  cout<<"\nlist2 contains: ";
  for(it = list2.begin(); it != list2.end(); it++)
    cout<<*it<<" ";

  //merging list2 into list1 
  list1.merge(list2);

  //displaying the result
  cout<<"\n\nAfter merging, list1 contains: \n";
  for(it = list1.begin(); it != list1.end(); it++)
    cout<<*it<<" ";

  return 0;
}

The output of the above code will be:

list1 contains: 10 20 50 60 
list2 contains: 10 30 45 75 

After merging, list1 contains: 
10 10 20 30 45 50 60 75

Example:

The example below describes the usage of second version of list::merge function, where int value of elements are used for sorting the elements.

#include <iostream>
#include <list>
using namespace std;
 
//a binary predicate to compare int value of elements
bool int_comp (double x, double y)
{ return ( int(x) < int(y) ); }

int main (){
  list<double> list1{3.5, 3.2, 5.5};
  list<double> list2{3.3, 5.9, 5.4};
  list<double>::iterator it;

  cout<<"list1 contains: ";
  for(it = list1.begin(); it != list1.end(); it++)
    cout<<*it<<" ";

  cout<<"\nlist2 contains: ";
  for(it = list2.begin(); it != list2.end(); it++)
    cout<<*it<<" ";

  //merging list2 into list1 
  list1.merge(list2, int_comp);

  //displaying the result
  cout<<"\n\nAfter merging, list1 contains: \n";
  for(it = list1.begin(); it != list1.end(); it++)
    cout<<*it<<" ";

  return 0;
}

The output of the above code will be:

list1 contains: 3.5 3.2 5.5 
list2 contains: 3.3 5.9 5.4 

After merging, list1 contains: 
3.5 3.2 3.3 5.5 5.9 5.4

❮ C++ <list> Library