Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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.

Fontes