std::merge
| Определено в заголовочном файле <algorithm>
|
||
| (1) | ||
| template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, |
(до C++20) | |
| template< class InputIt1, class InputIt2, class OutputIt > constexpr OutputIt merge( InputIt1 first1, InputIt1 last1, |
(начиная с C++20) | |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy, |
(2) | (начиная с C++17) |
| (3) | ||
| template< class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge( InputIt1 first1, InputIt1 last1, |
(до C++20) | |
| template< class InputIt1, class InputIt2, class OutputIt, class Compare> constexpr OutputIt merge( InputIt1 first1, InputIt1 last1, |
(начиная с C++20) | |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare> ForwardIt3 merge( ExecutionPolicy&& policy, |
(4) | (начиная с C++17) |
Объединяет два отсортированных диапазона [first1, last1) и [first2, last2), записывая элементы в новый диапазон начиная с d_first. На выходе получается диапазон [d_first, d_last), где d_last совпадает с d_first + (last1 - first1) + (last2 - first2). Новый диапазон удовлетворяет условиям std::is_sorted(d_first, d_last) и std::is_sorted(d_first, d_last, comp), соответственно.
О диапазоне можно говорить как об отсортированном в соответствии с функцией сравнения comp, если для каждого итератора it, указывающего на элемент последовательности, и любого неотрицательного целого числа n, такого, что it + n - это валидный итератор, указывающий на элемент последовательности, значение comp(*(it + n), *it) будет равно false.
operator<.comp.policy. true Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Эта функция объединения является "устойчивой" (stable), то есть обеспечивает на выходе такое расположение элементов из обоих исходных множеств, что элементы первого исходного множества предшествуют эквивалентным элементам из второго. Относительный порядок элементов сохраняется.
Поведение не определено если выходной диапазон пересекается с любым из входных диапазонов (входные диапазоны могут пересекаться).
Содержание |
[править] Параметры
| first1, last1 | — | первый диапазон элементов для объединения |
| first2, last2 | — | второй диапазон элементов для объединения |
| d_first | — | начало выходного диапазона |
| policy | — | политика исполнения, которую следует использовать (см. execution policy) |
| comp | — | функция сравнения, возвращающая true если первый аргумент меньше второго. Сигнатура функции сравнения должна быть эквивалентна следующей: bool cmp(const Type1 &a, const Type2 &b); Сигнатура на обязана содержать const &, однако, функция не может изменять переданные объекты. |
| Требования к типам | ||
-InputIt1, InputIt2 должен соответствовать требованиям InputIterator.
| ||
-ForwardIt1, ForwardIt2, ForwardIt3 должен соответствовать требованиям ForwardIterator.
| ||
-OutputIt должен соответствовать требованиям OutputIterator.
| ||
[править] Возвращаемое значение
OutputIt, указывающий на позицию вслед за последним скопированным элементом.
[править] Сложность
[править] Исключения
Перегрузки с шаблонным параметром, имеющим тип ExecutionPolicy обрабатывают ошибки следующим образом:
- Если при выполнении функции, вызванной в течение исполнения алгоритма, возникает исключение и
ExecutionPolicyравна одной из трёх стандартных политик, то вызывается std::terminate. Для любой другойExecutionPolicy, поведение определяется реализацией. - Если алгоритму не удаётся выделить память, то выбрасывается std::bad_alloc.
[править] Примечания
Работа данного алгоритма схожа с работой std::set_union: оба алгоритма принимают на вход два отсортированных диапазона, и формируют на выходе отсортированный диапазон из элементов обоих входных. Разница между ними в том, как они работают с элементами, оцениваемыми как эквивалентные при сравнении (см. LessThanComparable). Если любые эквивалентные значения появляются n раз в первом множестве, и m раз во втором, std::merge выдаст на выходе все n+m элементов, в отличие от std::set_union, который оставит максимум std::max(n, m). То есть std::merge оставляет ровно std::distance(first1, last1) + std::distance(first2, last2) элементов, а std::set_union может оставить меньше.
[править] Возможная реализация
См. так же реализации в libstdc++ и libc++.
| Первый вариант |
|---|
template<class InputIt1, class InputIt2, class OutputIt> OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first) { for (; first1 != last1; ++d_first) { if (first2 == last2) { return std::copy(first1, last1, d_first); } if (*first2 < *first1) { *d_first = *first2; ++first2; } else { *d_first = *first1; ++first1; } } return std::copy(first2, last2, d_first); } |
| Второй вариант |
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp) { for (; first1 != last1; ++d_first) { if (first2 == last2) { return std::copy(first1, last1, d_first); } if (comp(*first2, *first1)) { *d_first = *first2; ++first2; } else { *d_first = *first1; ++first1; } } return std::copy(first2, last2, d_first); } |
[править] Example
#include <iostream> #include <iterator> #include <algorithm> #include <vector> #include <random> #include <functional> int main() { // заполнить вектора случайными числами std::random_device rd; std::mt19937 mt(rd()); std::uniform_int_distribution<> dis(0, 9); std::vector<int> v1(10), v2(10); std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt))); std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt))); // отсортировать std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); // вывести v1 std::cout << "v1 : "; std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; // вывести v2 std::cout << "v2 : "; std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; // объединить std::vector<int> dst; std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst)); // вывести результат объединения std::cout << "dst: "; std::copy(dst.begin(), dst.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; }
Возможный вывод:
v1 : 0 1 3 4 4 5 5 8 8 9 v2 : 0 2 2 3 6 6 8 8 8 9 dst: 0 0 1 2 2 3 3 4 4 5 5 6 6 8 8 8 8 8 9 9
[править] See also
| объединяет два упорядоченных диапазона на месте (шаблон функции) | |
| (C++11) |
проверяет, отсортирован ли диапазон по возрастанию (шаблон функции) |
| вычисляет объединение двух множеств (шаблон функции) | |
| сортирует диапазон в порядке возрастания (шаблон функции) | |
| сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции) | |
