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.