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

CKTIS / C++

std::set_difference — diferença de intervalos ordenados

std::set_difference copia a diferença de dois intervalos ordenados para um destino separado. Tem em conta os duplicados: cada ocorrência equivalente no segundo intervalo elimina uma ocorrência do resultado do primeiro.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)

std::set_difference, declarado em <algorithm>, calcula a diferença direcional A − B, não a diferença simétrica. Aceita dois intervalos semiabertos de iteradores e um iterador de saída; não requer contentores std::set. As chamadas descritas aqui não utilizam uma política de execução.

Ambos os intervalos têm de estar ordenados segundo a mesma ordem: std::less{} por predefinição, ou comp na segunda forma. O comparador tem de definir uma ordem fraca estrita. Equivalência significa !comp(a, b) && !comp(b, a), não necessariamente a == b. O incumprimento do pré-requisito de ordenação provoca comportamento indefinido.

O algoritmo preserva os duplicados: para m elementos equivalentes no primeiro intervalo e n no segundo, copia os últimos max(m - n, 0) elementos do primeiro, pela ordem original. O resultado fica ordenado; as entradas permanecem inalteradas.

O destino não pode sobrepor-se a nenhum dos intervalos de entrada. Se o iterador de saída sobrescrever elementos de um intervalo, esse intervalo tem de conter elementos já existentes e modificáveis em número suficiente. No entanto, um iterador de saída não tem de referir-se a elementos existentes: std::back_inserter acrescenta elementos ao fim de um contentor e std::ostream_iterator escreve num fluxo. O iterador devolvido aponta para depois do resultado escrito. A complexidade é linear em relação ao comprimento combinado das entradas, sem incluir uma ordenação prévia.

Exemplos

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    const std::vector<int> a{1, 2, 2, 2, 4, 7};
    const std::vector<int> b{2, 2, 3, 7};
    std::vector<int> difference;

    std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                        std::back_inserter(difference));

    for (std::size_t i = 0; i < difference.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << difference[i];
    }
    std::cout << '\n';
}

Resultado

1 2 4

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