Функция merge

Функция merge объединяет два отсортированных диапазона в один отсортированный диапазон. В первый и второй параметры мы передаем итераторы начала первого и второго диапазонов, в третий и четвертый - итераторы конца первого и второго диапазонов, а в пятый - итератор начала результирующего диапазона. Элементы сравниваются с помощью оператора '<' либо пользовательского компаратора, который можно передать шестым параметром.

Функция возвращает итератор на элемент, следующий за последним скопированным элементом результата. Исходные диапазоны должны быть отсортированы, иначе поведение не определено.

Синтаксис

merge(first1, last1, first2, last2, res)
merge(first1, last1, first2, last2, res, comp)

Пример

Давайте объединим два отсортированных вектора {1, 3, 5} и {2, 4, 6} в один отсортированный вектор:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> a = {1, 3, 5};
	vector<int> b = {2, 4, 6};
	vector<int> res(6);
	
	merge(a.begin(), a.end(), b.begin(), b.end(), res.begin());
	
	for (int el : res) {
		cout << el << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

1 2 3 4 5 6

Пример

Давайте объединим два отсортированных вектора по убыванию {5, 3, 1} и {6, 4, 2}, передав пользовательский компаратор:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> a = {5, 3, 1};
	vector<int> b = {6, 4, 2};
	vector<int> res(6);
	
	merge(a.begin(), a.end(), b.begin(), b.end(), res.begin(),
		[](int x, int y) { return x > y; });
	
	for (int el : res) {
		cout << el << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

6 5 4 3 2 1

Пример

Давайте объединим два отсортированных вектора строк {"a", "c", "e"} и {"b", "d", "f"} в один вектор:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	vector<string> a = {"a", "c", "e"};
	vector<string> b = {"b", "d", "f"};
	vector<string> res(6);
	
	merge(a.begin(), a.end(), b.begin(), b.end(), res.begin());
	
	for (string el : res) {
		cout << el << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

"a" "b" "c" "d" "e" "f"

Смотрите также

функция inplace_merge,
которая сливает два отсортированных диапазона на месте
функция sort,
которая сортирует элементы диапазона
функция is_sorted,
которая проверяет, отсортирован ли диапазон
функция set_union,
которая строит объединение двух множеств