C++ STL 정리 - Set

# Definition

: set 컨테이너는 연관 컨테이너의 한 종류로, 아래 같은 형태로 정의되어 있다

template<
    class Key, 
    class Compare<Key> = std::less<Key>, 
    class Allocator = std::allocator<Key>
> class set;

기본적으로 set 은 중복을 허용하지 않으며, 

기본 정렬 방식은 std::less 이다.

set 은 red-black trees 를 기반으로 하기 때문에, 탐색, 삽입, 삭제에 대한 연산 시간복잡도가 O(logN) 이다.

 

# Header

#include <set>

 

 

# Iterator

begin, cbegin, end, cend, rbegin, crbegin, rend, crend 

8종류가 있다.

#include <iostream>
#include <set>
 
using namespace std;
 
int main() {
    set<int> s = {3,1,4,5,7,1,6,3};
    // s = {1,3,4,5,6,7}
    // set 이어서 중복 제거 및 std::less 에 따라 오름차순 정렬
    
    set<int>::iterator iter;
    
    for (iter = s.begin(); iter != s.end(); iter++) {
        cout << *iter << " "; // 결과 1 3 4 5 6 7 
    }
    cout << '\n';
    
    for (iter = s.cbegin(); iter != s.cend(); iter++) {
        cout << *iter << " "; // 결과 1 3 4 5 6 7
    }
    cout << '\n';
    
    set<int>::reverse_iterator riter;
    
    for (riter = s.rbegin(); riter != s.rend(); riter++) {
        cout << *riter << " "; // 결과 7 6 5 4 3 1
    }
    cout << '\n';
    
    for (riter = s.crbegin(); riter != s.crend(); riter++) {
        cout << *riter << " "; // 결과 7 6 5 4 3 1
    }
    
    return 0;
}

cbegin() 이나 begin() 이나 기능적으로는 똑같으나, 

반환 타입이 다른게 차이점이다.

 

cbegin(), cend() 는 const_iterator 를 반환하는 반면,

begin(), end() 는 iterator 를 반환한다.

 

다른 cend(), end() 나, rbegin(), crbegin() 도 마찬가지다.

 

출처 : https://en.cppreference.com/w/cpp/container/set/rend

 

# Capacity

#include <iostream>
#include <set>
 
using namespace std;
 
int main() {
    
    set<int> s;
    
    cout << " is s empty ? : " << s.empty() << '\n'; // 결과 true
    
    s.insert(4);
    s.insert(6);
    s.insert(91);
    
    cout << " s size ? : " << s.size() << '\n'; // 결과 3
    
    cout << " s max_size() : " << s.max_size() << '\n'; // 결과 4611.......
    
    return 0;
}

empty 는 비었는지 확인하는것이고, 반환 타입은 boolean

size 는 컨테이너 안에들어간 원소의 갯수를 리턴하며,

max_size() 는 해당 컨테이너가 최대로 수용할 수 있는 원소의 갯수다.

 

# Modifier

-1) insert, emplace

#include <iostream>
#include <set>
 
using namespace std;
 
void print_set(set<int> s) {
    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << '\n';
}
 
int main() {
    
    set<int> s;
    
    s.insert(76);
    s.insert(1);
    s.insert(42);
    
    print_set(s); // 결과 : 1 42 76
    
    pair<set<int>::iterator, bool> Pair;
    
    Pair = s.emplace(22);
    cout << *Pair.first << " " << Pair.second << '\n'; // 결과 : 22 1
    print_set(s); // 결과 : 1 22 42 76
    
    Pair = s.emplace(22);
    cout << *Pair.first << " " << Pair.second << '\n'; // 결과 : 22 0
    print_set(s); // 결과 : 1 22 42 76
    
    return 0;
}

insert 와 emplace 둘다 set 컨테이너에 값을 넣는다는 점은 같으나,

 

emplace 의 경우 리턴 타입이 pair<iterator, bool> 이다.

여기서 iterator 는 emplace 를 통해서 넣은 값의 위치 정보를 갖는 iterator 를 의미하며,

bool 은 emplace 를 할때, 그 값이 이미 중복된 값이 있었는지 없었는지를 의미하는 불 대수 값이다.

위 예제에서 처음엔 22 가 없었으므로, Pair.second 에 1(=true)이 출력되었고,

그 다음은 이미 22가 있기 때문에 0(=false) 이 출력되었다,

 

-2) erase

#include <iostream>
#include <set>
 
using namespace std;
 
int main()
{
    set<int> c = {1, 2, 3, 4, 5, 6, 7, 8, 9};
 
    // erase all odd numbers from c
    for(auto it = c.begin(); it != c.end(); ) {
        if(*it % 2 == 1)
            it = c.erase(it);
        else
            ++it;
    }
 
    for(int n : c) {
        cout << n << ' ';
    }
}

 

cppreference 에서 그대로 가져온 코드로 (en.cppreference.com/w/cpp/container/set/erase)

2로 나눠떨어지지 않는 원소들은 모두 제거하고 2의 배수만 출력하게 하는 코드이다.

 

-3) clear, swap

#include <iostream>
#include <set>
 
using namespace std;
 
void print_set(set<int> s) {
    if (s.empty()) {
        cout << "empty" << '\n';
        return;
    }
    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << '\n';
}
 
int main() {
    
    set<int> s;
    
    s.insert(76);
    s.insert(1);
    s.insert(42);
 
    print_set(s); // 결과 : 76 1 42
    
    s.clear();
    
    print_set(s); // 결과 : empty
    
    set<int> s1 = {2,3,4};
    set<int> s2 = {400, 9, 12};
    
    cout << "--- before swap ---" << '\n';
    print_set(s1); // 결과 : 2 3 4 
    print_set(s2); // 결과 : 9 12 400
    
    s1.swap(s2);
    
    cout << "--- after swap ---" << '\n';
    print_set(s1); // 결과 : 9 12 400
    print_set(s2); // 결과 : 2 3 4
 
    return 0;
}

 

 

clear 는 원소 전부를 지우고,

swap 은 서로 다른 set 끼리 원소를 교환한다.

 

- 4) extract

#include <algorithm>
#include <iostream>
#include <set>
 
using namespace std;
 
int main()
{
    set<int> cont{1, 2, 3};
 
    auto print = [](const int& n) { cout << " " << n; };
 
    cout << "Start:";
    for_each(cont.begin(), cont.end(), print);
    cout << '\n';
 
    // Extract node handle and change key
    auto nh = cont.extract(1);
    nh.value() = 4; 
 
    cout << "After extract and before insert:";
    for_each(cont.begin(), cont.end(), print);
    cout << '\n';
 
    // Insert node handle back
    cont.insert(move(nh));
 
    cout << "End:";
    for_each(cont.begin(), cont.end(), print);
    cout << '\n';
}

 

cppreference 에서 그대로 가져온 코드로 (en.cppreference.com/w/cpp/container/set/extract)

extract 는 추출할 키값을 설정해서 해당 node 를 꺼내오며 리턴타입은 node handle 이다.

위 예제를 보면 알 수 있듯 특정 노드만 꺼내와서 값을 변경하여 다시 넣는 것을 알 수 있다.

extract 는 C++ 17 부터 사용이 가능하다.

 

(람다식에 관한 내용은 아래 링크 참조)

(modoocode.com/196)

 

- 5) merge

#include <iostream>
#include <set>
 
using namespace std;
 
// print out a container
template <class Os, class K>
Os& operator<<(Os& os, const std::set<K>& v) {
    os << '[' << v.size() << "] {";
    bool o{};
    for (const auto& e : v)
        os << (o ? ", " : (o = 1, " ")) << e;
    return os << " }\n";
}
 
int main()
{
    set<char> p = { 'C', 'B', 'B', 'A' };
    set<char> q = { 'E', 'D', 'E', 'C' };
 
    cout << "p: " << p << "q: " << q;
    // 출력 결과
    // p [3] {A, B, C}
    // q [3] {C, D, E}
 
    p.merge(q);
 
    cout << "p.merge(q);\n" << "p: " << p << "q: " << q;
    // 출력 결과
    // p [5] {A, B, C, D, E}
    // q [1] {C}
}

 

코드 출처 : en.cppreference.com/w/cpp/container/set/merge

 

출력 결과에서 예상할 수 있듯, merge 는 두 set 컨테이너 간에 합치는 함수이다.

x.merge(y) 하면 x 에는 합집합의 결과가, y 에는 교집합의 결과가 나오게 된다.

merge 는 C++ 17 부터 가능하다.

 

 

# LookUp

#include <iostream>
#include <set>
 
using namespace std;
 
int main() {
    set<char> s = {'A','B','C','C','D','A','A'};
    cout << s.count('A') << '\n'; // 결과 : 1
    
    set<char>::iterator iter = s.find('B');
    cout << *iter << '\n'; // 결과 : B
    
    set<char>::iterator low = s.lower_bound('C');
    set<char>::iterator up = s.upper_bound('C');
    
    cout << *low << " " << *up << '\n'; // 결과 C D
    
    return 0;
}

 

count 는 인자 값과 동일한 원소의 갯수가 몇개인지 리턴한다. (근데 set 은 어차피 만들어질때부터 중복을 제거하고 정렬하는데 이게 왜 있는지 모르겠다)

 

find 는 인자 값과 동일한 키에 대응하는 iterator 를 반환한다.

위 예제에선 1번째 인덱스에 해당하는 iterator 가 반환된다.

 

lower_bound('C') 는 'C' 보다는 작지 않은 원소가 최초로 나오는 지점의 iterator 를 반환한다.

(작지 않은 경우 이므로 크거나 같은 경우에 해당하는 최초의 위치의 iterator 를 리턴한다)

 

upper_bound('C') 는 'C' 보다 큰 값이 최초로 나오는 원소의 iterator 를 반환한다.

 

 

 

- References

1. en.cppreference.com/w/cpp/container/set

2. modoocode.com/196