CKTIS / C++
std::merge — fusão estável de intervalos ordenados
std::merge, de <algorithm>, copia dois intervalos ordenados para um intervalo de saída separado. Preserva os duplicados e a estabilidade, e devolve um iterador imediatamente após o último elemento escrito.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);std::merge funde [first1, last1) e [first2, last2), escrevendo todos os elementos a partir de result. Ambas as entradas têm de estar previamente ordenadas segundo a mesma ordem: crescente por predefinição ou a ordem especificada por comp. O comparador tem de definir uma ordem fraca estrita. Entradas não ordenadas violam as pré-condições do algoritmo; a função não ordena primeiro as entradas.
A fusão é estável: preserva a ordem dos elementos em cada entrada e os elementos com chaves equivalentes do primeiro intervalo surgem antes dos do segundo. Equivalência significa que nem comp(a, b) nem comp(b, a) é verdadeiro. Os duplicados permanecem na saída.
O intervalo de saída não pode sobrepor-se a nenhum dos intervalos de entrada. Disponibilize espaço para a soma dos seus comprimentos ou utilize um iterador de inserção adequado. Chamar apenas reserve() num vetor não cria elementos nos quais seja possível escrever através de begin(). O iterador devolvido aponta para a posição imediatamente após o último elemento escrito.
Para as sobrecargas aqui abordadas, sem uma política de execução, o trabalho é linear em relação ao número total de elementos N, com um máximo de N - 1 comparações quando N > 0. Não confunda esta função com std::inplace_merge, que funde dois subintervalos ordenados adjacentes dentro do mesmo intervalo. O exemplo utiliza sintaxe compatível com C++23; o projeto de norma citado é atualizado e pode também incluir extensões posteriores.
Exemplos
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array<int, 3> a{1, 3, 5};
const std::array<int, 3> b{2, 3, 6};
std::array<int, 6> result{};
const auto end = std::merge(a.begin(), a.end(),
b.begin(), b.end(), result.begin());
for (auto it = result.begin(); it != end; ++it) {
if (it != result.begin()) {
std::cout << ' ';
}
std::cout << *it;
}
std::cout << '\n';
}
Resultado
1 2 3 3 5 6
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.