std::set intersection

Angol

Főnév

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

(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.

🕹️ Szintaxis

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.

⚙️ Hogyan működik?

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.

Időkomplexitás:

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

📝 Példa

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

Kimenet:

Metszet eredménye: 3 4 5

Mire jó?

✅ 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.

Fontos megjegyzések

✅ 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.

Kapcsolódó algoritmusok

Algoritmus	Művelet
`std::set_union`	Unió (összes elem egyszer)
`std::set_intersection`	Metszet (csak közös elemek)
`std::set_difference`	Különbség (csak az elsőben lévő elemek)
`std::set_symmetric_difference`	Szimmetrikus különbség (csak az egyikben szereplő elemek)

Használati minta vectorral

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));

Összefoglalás

Tulajdonság	Részlet
Algoritmus neve	`std::set_intersection`
Mit csinál	Kiszámítja a metszetet (közös elemek)
Bemenet	2 db rendezett tartomány
Kimenet	Rendezett tartomány (közös elemek)
Duplikátumok	Igen, a kisebb előfordulás szerint
Időkomplexitás	O(n1 + n2)

További információk

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)