# std::list<T,Allocator>::merge

> C++ Atlas: `cppatlas.com/w/cpp/container/list/merge` | Source: https://en.cppreference.com/w/cpp/container/list/merge | Domain: Containers | Standards: C++98, C++11, C++14, C++20

The function does nothing if other refers to the same object as *this.

## Official Specification Summary (cppreference)

```cpp
void merge( list& other ); // (1)

void merge( list&& other ); // (2) (since C++11)

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

template< class Compare >
void merge( list&& other, Compare comp ); // (4) (since C++11)
```

The function does nothing if `other` refers to the same object as `*this`.

Otherwise, merges `other` into `*this`. Both lists should be sorted. No elements are copied, and the container `other` becomes empty after the merge. This operation is stable: for equivalent elements in the two lists, the elements from `*this` always precede the elements from `other`, and the order of equivalent elements of `*this` and `other` does not change.

No iterators or references become invalidated. The pointers and references to the elements moved from `*this`, as well as the iterators referring to these elements, will refer to the same elements of `*this`, instead of `other`.

1,2) Elements are compared using `std::less<T>()` (until C++14) `std::less<>()` (since C++14).

3,4) Elements are compared using `comp`.

If `*this` or `other` is not sorted with respected to the corresponding comparator, or `get_allocator() != other.get_allocator()`, the behavior is undefined.

### Parameters

- `other` - another container to merge
- `comp` - comparison function object (i.e. an object that satisfies the requirements of *Compare*) which returns `true` if the first argument is *less* than (i.e. is ordered *before*) the second.

  The signature of the comparison function should be equivalent to the following:

  `bool cmp(const Type1& a, const Type2& b);`

  While the signature does not need to have `const&`, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, `Type1&` is not allowed, nor is `Type1` unless for `Type1` a move is equivalent to a copy (since C++11)).
  The types `Type1` and `Type2` must be such that an object of type `list<T, Allocator>::const_iterator` can be dereferenced and then implicitly converted to both of them.

**Type requirements**

- `Compare` must meet the requirements of *Compare*.

### Return value

(none)

### Exceptions

If an exception is thrown for any reason, these functions have no effect (strong exception safety guarantee). Except if the exception comes from a comparison.

### Complexity

If `other` refers to the same object as `*this`, no comparisons are performed.

Otherwise, given N as `std::distance(begin(), end())` and R as `std::distance(other.begin(), other.end())`:

1,2) At most N+R-1 comparisons using `operator<`.

3,4) At most N+R-1 applications of the comparison function `comp`.

### Example

```cpp
#include <iostream>
#include <list>

std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
    for (const int i : list)
        ostr << ' ' << i;
    return ostr;
}

int main()
{
    std::list<int> list1 = {5, 9, 1, 3, 3};
    std::list<int> list2 = {8, 7, 2, 3, 4, 4};

    list1.sort();
    list2.sort();
    std::cout << "list1: " << list1 << '\n';
    std::cout << "list2: " << list2 << '\n';

    list1.merge(list2);
    std::cout << "merged:" << list1 << '\n';
}
```

Output:

```text
list1:  1 3 3 5 9
list2:  2 3 4 4 7 8
merged: 1 2 3 3 3 4 4 5 7 8 9
```

### Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

| DR | Applied to | Behavior as published | Correct behavior |
| --- | --- | --- | --- |
| LWG 300 | C++98 | the effect when `*this` and `other` refer to the same object was not specified | specified as no-op |
| LWG 1207 | C++98 | it was unclear whether iterators and/or references will be invalidated | keep valid |
| LWG 1215 | C++98 | O(1) node moving could not be guaranteed if `get_allocator() != other.get_allocator()` | the behavior is undefined in this case |
| LWG 3088 | C++98 | `operator<` could misbehave for pointer elements | implementation-defined strict total order used |

### See also

- [`splice`](https://en.cppreference.com/w/cpp/container/list/splice): moves elements from another `list` (public member function)
- [`merge`](https://en.cppreference.com/w/cpp/algorithm/merge): merges two sorted ranges (function template)
- [`inplace_merge`](https://en.cppreference.com/w/cpp/algorithm/inplace_merge): merges two ordered ranges in-place (function template)
- [`ranges::merge`](https://en.cppreference.com/w/cpp/algorithm/ranges/merge) (C++20): merges two sorted ranges (algorithm function object)
- [`ranges::inplace_merge`](https://en.cppreference.com/w/cpp/algorithm/ranges/inplace_merge) (C++20): merges two ordered ranges in-place (algorithm function object)

---
Attribution: content from https://en.cppreference.com/w/cpp/container/list/merge (cppreference.com), licensed under CC-BY-SA 3.0 and GFDL. Modified: converted to markdown, study notes added. Offline snapshot of 9 February 2025.