Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::set_difference — rozdíl seřazených rozsahů

std::set_difference zkopíruje rozdíl dvou seřazených rozsahů do samostatného cíle. Zohledňuje duplicity: každý ekvivalentní prvek ve druhém rozsahu zruší jeden výskyt z výsledku prvního rozsahu.

Verze: C++23; repository compiler flag, production runtime not attested

Syntaxe

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

std::set_difference z hlavičky <algorithm> počítá směrový rozdíl A − B, nikoli symetrický rozdíl. Přijímá dva polouzavřené rozsahy iterátorů a výstupní iterátor; kontejnery std::set nejsou potřeba. Zde popsaná volání nepoužívají zásadu provádění.

Oba rozsahy musí být seřazeny podle stejného uspořádání: ve výchozím stavu podle std::less{}, ve druhé variantě podle comp. Komparátor musí definovat striktní slabé uspořádání. Ekvivalence znamená !comp(a, b) && !comp(b, a), nikoli nutně a == b. Porušení předpokladu seřazení vede k nedefinovanému chování.

Algoritmus zachovává duplicity: je-li v prvním rozsahu m ekvivalentních prvků a ve druhém n, zkopíruje posledních max(m - n, 0) prvků z prvního rozsahu v jejich původním pořadí. Výsledek je seřazený; vstupy zůstanou beze změny.

Cíl se nesmí překrývat s žádným vstupním rozsahem. Pokud výstupní iterátor přepisuje prvky rozsahu, musí tento rozsah obsahovat dostatek již existujících prvků, do nichž lze zapisovat. Výstupní iterátor ale nemusí odkazovat na existující prvky: std::back_inserter přidává prvky na konec kontejneru a std::ostream_iterator zapisuje do proudu. Vrácený iterátor ukazuje za zapsaný výsledek. Složitost je lineární vzhledem k součtu délek vstupů, bez započtení případného předchozího řazení.

Příklady

#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';
}

Výsledek

1 2 4

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje