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) Элементы сравниваются с помощью std::less<T>()(до C++14)std::less<>()(начиная с C++14).

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

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

Параметры

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

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

отсутствует

Исключения

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

Сложность

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

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

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

3,4) Не более \(\scriptsize N+R-1\)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()`	в этом случае поведение не определено
LWG 3088	C++98	operator< мог некорректно работать для элементов-указателей	используется определяемый реализацией строгий полный порядок

См. также

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

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