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

void merge( list& other );	(1)
void merge( list&& other );	(2)	(с C++11)
template< class Compare > void merge( list& other, Compare comp );	(3)
template< class Compare > void merge( list&& other, Compare comp );	(4)	(с C++11)

Функция ничего не делает, если other ссылается на тот же объект, что и *this.

В противном случае, объединяет other в *this. Оба списка должны быть отсортированы. Элементы не копируются, а контейнер other становится пустым после слияния. Данная операция устойчива: для эквивалентных элементов в двух списках, элементы из *this всегда предшествуют элементам из other, и порядок эквивалентных элементов из *this и other не изменяется.

Итераторы или ссылки не становятся недействительными. Указатели и ссылки на элементы, перемещённые из *this, а также итераторы, ссылающиеся на эти элементы, будут ссылаться на те же элементы в *this, а не в other.

1,2) Элементы сравниваются с использованием operator<.

3,4) Элементы сравниваются с использованием comp.

Если *this или other не отсортированы относительно соответствующего компаратора, или get_allocator() != other.get_allocator(), поведение не определено.

Параметры

other	-	другой контейнер для слияния
comp	-	объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true` если первый аргумент меньше (т.е. упорядочен раньше) второго. Подпись функции сравнения должна быть эквивалентна следующему: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не обязана содержать const&, функция не должна изменять передаваемые ей объекты и должна быть способна принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` недопустимо, также как и `Type1` за исключением случаев, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа list<T, Allocator>::const_iterator мог быть разыменован, а затем неявно преобразован в оба из них.
Требования к типу
-`Compare` должен удовлетворять требованиям Compare.

Возвращаемое значение

(нет)

Исключение

Если возникает исключение по любой причине, эти функции не имеют эффекта (сильная гарантия безопасности исключений). За исключением случая, когда исключение исходит из сравнения.

Сложность

Если other ссылается на тот же объект, что и *this, сравнения не выполняются.

В противном случае, при \(N\) как std::distance(begin(), end()) и \(R\) как std::distance(other.begin(), other.end()):

1,2) Максимум \(N+R-1\) сравнений с использованием operator<.

3,4) Максимум \(N+R-1\) применений функции сравнения comp.

Пример

#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';
}

Вывод:

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

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применяется к	Поведение, как опубликовано	Корректное поведение
LWG 300	C++98	эффект, когда `*this` и `other` ссылаются на один и тот же объект, не был указан	указано как операция без действия
LWG 1207	C++98	неясно, будут ли итераторы и/или ссылки аннулированы	сохраняются действительными
LWG 1215	C++98	перемещение узлов O(1) не могло быть гарантировано, если `get_allocator() != other.get_allocator()`	поведение в этом случае неопределено

См. также

splice	перемещает элементы из другого `list` (публичный член-функция)
merge	объединяет два отсортированных диапазона (шаблон функции)
inplace_merge	объединяет два упорядоченных диапазона на месте (шаблон функции)
ranges::merge (C++20)	объединяет два отсортированных диапазона (niebloid)
ranges::inplace_merge (C++20)	объединяет два упорядоченных диапазона на месте (niebloid)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/list/merge