Cpp Libs List Merge
📅 2026-06-22 | 📂 C++
# C++ std::list::merge() Function
The `std::list::merge` function is a built-in member function of the C++ `` container. It is designed to **merge two sorted lists** into a single sorted list.
Because `std::list` is implemented as a doubly-linked list, `std::list::merge` is highly efficient. Instead of copying or moving elements physically in memory, it simply splices the internal node pointers of the two lists.
---
## Syntax and Parameters
### Function Signatures
```cpp
// Overload 1: Merges using operator< (ascending order by default)
void merge(list& other);
void merge(list&& other); // Since C++11
// Overload 2: Merges using a custom comparison function
template
void merge(list& other, Compare comp);
template
void merge(list&& other, Compare comp); // Since C++11
```
### Parameters
* **`other`**: Another sorted `std::list` of the same type to be merged into the current list.
* **`comp`**: A binary predicate (comparison function) that defines the sorting order. It should accept two arguments of the same type as the list elements and return `true` if the first element should go before the second, and `false` otherwise.
### Return Value
* **`void`**: The function does not return any value.
### Key Behavior
1. **Precondition**: Both the calling list (`*this`) and the target list (`other`) **must be sorted** according to the same sorting criteria before calling `merge`. If they are not sorted, the behavior is undefined.
2. **Transfer of Ownership**: After the operation, all elements from `other` are transferred to the calling list. **The `other` list is left empty**.
3. **Stability**: The merge is stable. If there are equivalent elements in both lists, elements from the calling list (`*this`) will always precede elements from `other` in the merged list.
---
## Code Examples
### Example 1: Merging Two Ascending Sorted Lists
This example demonstrates how to merge two lists sorted in ascending order using the default `merge(other)` overload.
```cpp
#include
#include
int main() {
std::list list1 = {1, 3, 5, 7, 9};
std::list list2 = {2, 4, 6, 8, 10};
std::cout << "list1 before merge: ";
for(int n : list1) std::cout << n << " ";
std::cout << std::endl;
std::cout << "list2 before merge: ";
for(int n : list2) std::cout << n << " ";
std::cout << std::endl;
// Merge list2 into list1
list1.merge(list2);
std::cout << "list1 after merge: ";
for(int n : list1) std::cout << n << " ";
std::cout << std::endl;
// Verify that list2 is now empty
std::cout << "list2 size after merge: " << list2.size() << std::endl;
return 0;
}
```
#### Expected Output:
```text
list1 before merge: 1 3 5 7 9
list2 before merge: 2 4 6 8 10
list1 after merge: 1 2 3 4 5 6 7 8 9 10
list2 size after merge: 0
```
---
### Example 2: Merging with a Custom Comparison Function (Descending Order)
If your lists are sorted in descending order, you must provide a custom comparison function (such as `std::greater`) to the `merge` function.
```cpp
#include
#include
#include // Required for std::greater
int main() {
// Both lists must be pre-sorted in descending order
std::list a = {9, 7, 5, 3};
std::list b = {8, 6, 4, 2, 1};
// Merge using std::greater to maintain descending order
a.merge(b, std::greater());
std::cout << "Merged list (descending): ";
for(int n : a) std::cout << n << " ";
std::cout << std::endl;
std::cout << "Is list b empty? " << (b.empty() ? "Yes" : "No") << std::endl;
return 0;
}
```
#### Expected Output:
```text
Merged list (descending): 9 8 7 6 5 4 3 2 1
Is list b empty? Yes
```
---
## Important Considerations
1. **Pre-sorting Requirement**: If either list is not sorted prior to calling `merge`, the function will still execute, but the resulting list will not be fully sorted, violating the function's post-condition. Always call `list::sort()` first if you are unsure of the order.
2. **Self-merging**: Merging a list into itself (e.g., `list1.merge(list1)`) is undefined behavior or a no-op depending on the compiler implementation. Avoid doing this.
3. **Iterator Validity**: Iterators and references to the elements transferred from `other` remain valid, but they now point to elements inside the calling list instead of `other`.
4. **Complexity**:
* If `&other == this`, the function does nothing.
* Otherwise, the complexity is at most $O(N + M - 1)$ comparisons, where $N$ is the size of the calling list and $M$ is the size of `other`. This makes it highly efficient compared to copying and re-sorting.
YouTip