[Mastering C++ Programming] - Set

• 집합 컨테이너는 고유한 값만 정렬된 방식으로 저장합니다.
• 집합은 값을 키로 사용하여 값을 구성합니다. 
• 집합 컨테이너는 변경할 수 없습니다. 
• 즉, 집합에 저장된 값은 수정할 수 없습니다. 
• 그러나 값은 삭제할 수 있습니다. 
• 세트는 일반적으로 balanced BST의 한 형태인 레드-블랙 트리 데이터 구조를 사용합니다. 
• 집합 작업의 시간 복잡도는 O(logN)로 보장됩니다.
  
  
• 코드 예제는 아래와 같습니다.

#include <iostream>
#include <set>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

int main( ) {
    set<int> s1 = { 1, 3, 5, 7, 9 };
    set<int> s2 = { 2, 3, 7, 8, 10 };

    vector<int> v( s1.size() + s2.size() );
        
    cout << "\nFirst set values are ..." << endl;
    copy ( s1.begin(), s1.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl;

    cout << "\nSecond set values are ..." << endl;
    copy ( s2.begin(), s2.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl;

    auto pos = set_difference ( s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin() ); 
    v.resize ( pos - v.begin() );

    cout << "\nValues present in set one but not in set two are ..." << endl;
    copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl; 

    v.clear();

    v.resize ( s1.size() + s2.size() );

    pos = set_union ( s1.begin(), s1.end(), s2.begin(), s2.end(), v.begin() );

    v.resize ( pos - v.begin() );

    cout << "\nMerged set values in vector are ..." << endl;
    copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, "\t" ) );
    cout << endl; 

    return 0;
}

 

• 결과는 아래와 같다.

First set values are ...
1   3   5   7   9

Second set values are ...
2   3   7   8   10

Values present in set one but not in set two are ...
1   5   9

Merged values of first and second set are ...
1   2   3   5   7   8   9  10

 

• set_difference() 알고리즘은 세트 s1에만 있고 s2에는 없는 값으로 벡터 v를 채웁니다. 
• 반복자 pos는 벡터의 마지막 요소를 가리킵니다. 
• 따라서 벡터 크기 조정은 벡터의 추가 공간이 제거되도록 합니다.
• set_union() 알고리즘은 세트 s1 및 s2의 내용을 벡터로 병합하고 벡터는 병합된 값에만 맞도록 크기를 조정합니다.

 

• API는 아래와 같다.