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

void merge( forward_list& other );	(1)	(начиная с C++11)
void merge( forward_list&& other );	(2)	(начиная с C++11)
template< class Compare > void merge( forward_list& other, Compare comp );	(3)	(начиная с C++11)
template< class Compare > void merge( forward_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&, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` не допускается, как и `Type1`, за исключением случая, когда для `Type1` перемещение эквивалентно копированию(начиная с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа forward_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 <forward_list>
 
std::ostream& operator<<(std::ostream& ostr, const std::forward_list<int>& list)
{
    for (const int i : list)
        ostr << ' ' << i;
    return ostr;
}
 
int main()
{
    std::forward_list<int> list1 = {5, 9, 1, 3, 3};
    std::forward_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++.

Отчёт об ошибке	Применяется к	Опубликованное поведение	Корректное поведение
LWG 2045	C++11	Перемещение узлов за O(1) не могло быть гарантировано, если `get_allocator() != other.get_allocator()`	в этом случае поведение не определено
LWG 3088	C++11	эффект, если `*this` и `other` ссылаются на один и тот же объект, не был определён operator< мог некорректно работать для указателей в качестве элементов	определён как отсутствие эффекта используется порядок, определяемый реализацией и являющийся строгим полным порядком

См. также

splice_after	перемещает элементы из другого `forward_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/forward_list/merge