std::set intersection

std::set intersection (tsz. std::set intersections)

1. (informatika) A std::set_intersection a C++ STL egyik halmazművelet algoritmusa, amely két rendezett tartomány metszetét számítja ki.

👉 Metszet = azok az elemek, amelyek mindkét tartományban előfordulnak.

Az eredmény:

• Csak azok az elemek, amelyek mind az elsőben, mind a másodikban benne vannak.
• Az elemek az eredményben is rendezett sorrendben lesznek.

std::set_intersection(first1, last1, first2, last2, result);

• first1, last1 → első tartomány kezdete és vége (iterátorok).
• first2, last2 → második tartomány kezdete és vége (iterátorok).
• result → kimeneti iterátor, pl. std::back_inserter vagy std::inserter.

• Mindkét bemenetet párhuzamosan bejárja.
• Ha egy elem mindkét tartományban szerepel, az bekerül az eredménybe.
• Ha az egyik tartományban van csak → kihagyja.
• Az algoritmus garantálja, hogy az eredmény rendezett lesz.

• O(n1 + n2), ahol n1 és n2 a két tartomány mérete.

#include <iostream>
#include <set>
#include <algorithm>

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};
    std::set<int> intersectionSet;

    std::set_intersection(set1.begin(), set1.end(),
                          set2.begin(), set2.end(),
                          std::inserter(intersectionSet, intersectionSet.begin()));

    std::cout << "Metszet eredménye: ";
    for (int num : intersectionSet) {
        std::cout << num << " ";
    }

    return 0;
}

Metszet eredménye: 3 4 5

✅ Halmazműveletekhez → közös elemek keresése. ✅ Két adatforrásból a közös elemek kigyűjtése. ✅ Duplikált adatellenőrzés → mely elemek fordulnak elő mindkét helyen. ✅ Statisztikai elemzés → közös jellemzők megtalálása.

✅ A bemeneti tartományoknak rendezettnek kell lenniük → ha nem rendezettek, először std::sort. ✅ Ha egy elem többször is előfordul → a kisebb előfordulási számot veszi figyelembe (halmazelméleti viselkedés):

• Pl.: {1,2,2,3} és {2,2,2,4} → metszet: {2,2}

✅ Az eredmény rendezett.

A std::set_intersection nem csak std::set-tel használható, hanem bármilyen rendezett tartománnyal (pl. std::vector):

std::vector<int> v1 = {1, 2, 3, 4};
std::vector<int> v2 = {3, 4, 5, 6};

std::vector<int> result;
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));

• std::set intersection - Szótár.net (en-hu)
• std::set intersection - Sztaki (en-hu)
• std::set intersection - Merriam–Webster
• std::set intersection - Cambridge
• std::set intersection - WordNet
• std::set intersection - Яндекс (en-ru)
• std::set intersection - Google (en-hu)
• std::set intersection - Wikidata
• std::set intersection - Wikipédia (angol)