[C++] STL 자료구조: Set, Map

set, map은 자가 균형 이진 탐색 트리(BBST, self-balancing binary search tree)로 구현되어있는 자료구조이다. BBST의 일종인 레드-블랙 트리(Red-black tree)로 구현되어 있다. 이는 원소들이 정렬되어 있다는 이진 탐색 트리의 성질과 트리의 높이를 최대한 작게 유지한다는 균형 이진 트리의 성질을 모두 지닌다. (만약 set, map을 직접 구현해야 한다면 보통 red-black tree 대신 treap, skip-list, splay tree 등을 이용한다.)

대소관계가 정의된 자료형의 삽입, 삭제, 검색을 O(logn)에 처리할 수 있다.

단, S[i]나 S.begin() + i와 같은 연산을 지원하지 않아서 i번째 원소에 빠르게 접근할 수 없다.

​

set, map은 1)원소의 삽입, 삭제가 빈번하게 일어나면서 2)원소의 정렬 상태를 유지해야 하고, 3)특정 원소를 검색하거나 수정할 필요가 있을 때 주로 사용된다. 이때 항상 내부의 원소들이 정렬되어있다는 두 번째 성질이 매우 유용하다.

set과 map의 차이점은 set은 컨테이너 내부의 원소들을 저장만 하고, map은 원소(key)와 원소에 대응되는 value를 같이 저장한다는 것이다. set은 보통 vector처럼 원소만 저장할 때, map은 (key, val) pair를 순서대로 저장하면서 M[key] = val와 같이 key로 val을 접근할 때 사용한다.

 

multiset, multimap

set, map은 같은 원소가 중복될 수 없다. 예를 들어 set<int> S = { 1, 1, 2, 3 }으로 선언하면 S에는 { 1, 2, 3 }이 들어가고, map도 마찬가지로 같은 key값을 갖는 여러 { key, val }쌍이 존재할 수 없다.

set, map에서 중복된 원소를 사용하고 싶다면 multiset, multimap을 이용한다. multiset<int> MS = { 1, 1, 2, 3 } 으로 선언한다.

이때 만약 중복된 원소가 여러 개 있을 때 해당 원소 1개를 지우고 싶다면 S.erase(S.find(3))과 같이 iterator를 이용해야 한다. S.erase(3)과 같이 key값을 이용해 지우는 경우는 중복된 원소가 전부 지워진다!

multimap의 경우에는 []연산자가 없기 때문에 map처럼 []연산자를 이용해 key로 value를 찾거나 삽입할 수 없다. 일반적으로 multimap을 잘 사용하지 않는다.

 

set, map 의 생성자

​

1. set<int> S;

2. set<int> S(v.begin(), v.end()); // [start, end) 범위의 원소를 갖는다

3. set<int, Compare> S(cmp); // cmp의 자료형은 Compare

4. set<int> S{ 1, 2, 3 }; 또는 set<int> S = { 1, 2, 3 };

​

1. map<string, int> M;

2. map<string, int> M(v.begin(), v.end()); // v의 원소의 자료형은 pair<string, int>

3. map<string, int, Compare> M(cmp); // cmp의 자료형은 Compare, Compare는 greater<string> 등

 

set의 멤버 함수

int main() {

fastio;

set<int> S = { 1, 2 }; // 초기화

auto [it1, flag1] = S.insert(2); // S = { 1, 2 }

// it1은 삽입된 위치를 가리키므로 *it1 == 2, 삽입이 성공했는지 여부를 나타내는 boolean flag1 == 0

auto [it2, flag2] = S.insert(3); // S = { 1, 2, 3 }, *it2 == 3, flag2 == 1

it1 = S.erase(it1); // S = { 1, 3 }, it1==2였는데 erase되니까 다음 요소를 가리킴 *it1 == 3

auto cnt = S.erase(3); // S = { 1 }, cnt == 1 (남은 원소의 갯수)

 

cout << "S.size() : " << S.size() << '\n'; // 1

cout << "S.empty() : " << S.empty() << '\n'; // 0

S.clear();

 

for (auto& i : { 3, 1, 4, 1, 5 }) S.insert(i); // S = { 1, 3, 4, 5 } 중복이라 1이 들어가지 않음

for (auto& i : S) cout << i << ' '; cout << '\n'; // 1 3 4 5

 

if (S.count(2)) cout << "found 2" << '\n'; // x

if (S.count(3)) cout << "found 3" << '\n'; // o

 

auto lo = S.lower_bound(3); // 값이 3 이상인 첫 번째 원소를 가리키는 반복자를 반환

// *lo == 3, *prev(lo) < 3 <= *lo랑 같은 의미인데 *prev(lo)는 3보다 작은 마지막 원소를 가리킨다. 

auto hi = S.upper_bound(3); // 값이 3을 초과하는 첫 번째 원소를 가리키는 반복자를 반환

// *hi == 4, *prev(hi) <= 3 < *hi 랑 같은 의미인데 여기서 prev(hi)는 4 이전이므로 3이다.

}

 

map의 멤버 함수

int main() {

fastio;

map<string, int> M;

M["abc"] = 3; // == M.insert({ "abc", 3 })인데 abc가 문자열 키고 3이 대응하는 값

cout << M["abc"] << '\n'; // 3

M["abc"] = 4;

cout << M["abc"] << '\n'; // 4

 

auto it = M.erase("abc"); // M = { }, it == M.end()

M["hi"] = 123; // M = { { "hi", 123 } }

auto cnt = M.erase("hi"); // M = { }, cnt == 1

 

cout << "M.size() : " << M.size() << '\n'; // 0

cout << "M.empty() : " << M.empty() << '\n'; // 1

M.clear();

 

vector<string> s{ "ab", "cde", "fghi" };

vector<int> v{ 3, 1, 4 };

for (int i = 0; i < 3; i++) M[s[i]] = v[i];

for (auto& [a, b] : M) cout << '(' << a << ',' << b << ')' << ' '; cout << '\n'; // (ab,3) (cde,1) (fghi,4)

 

if (M.count("abc")) cout << "found abc" << '\n'; // x

if (M.count("cde")) cout << "found cde" << '\n'; // o

}

이외에도

- insert(val) : val을 삽입, val을 가리키는 iterator와 val의 삽입 여부(bool)를 pair로 반환. O(logn)

- erase(it) : 매개변수로 받은 iterator 위치의 원소를 삭제, 원래 위치의 다음 원소의 iterator를 반환. O(logn)

- erase(key) : 컨테이너 내의 매개변수로 받은 key을 모두 삭제, 삭제한 원소의 개수를 반환. O(logn)

​

- size : set, map의 크기를 size_t 자료형으로 반환.

- empty : set, map이 비어있는지 여부를 bool 자료형으로 반환.

- clear : set, map의 모든 원소를 삭제.

​

- begin : set, map의 첫 번째 원소를 가리키는 iterator를 반환. O(1)

- end : set, map의 마지막 원소의 다음 칸을 가리키는 iterator를 반환. O(1)

- rbegin : begin의 reverse_iterator 버전. O(1)

- rend : end의 reverse_iterator 버전. O(1)

​

- find : val을 가리키는 iterator를 반환. 만약 val이 없다면 end()를 반환. O(logn)

- count : set, map 내부의 val의 개수를 반환. multiset, multimap이 아니라면 있으면 1, 없으면 0. O(logn)

​

- lower_bound : set, map의 lower_bound를 반환. O(logn)

- upper_bound : set, map의 upper_bound를 반환. O(logn)

- equal_range : set, map의 lower_bound, upper_bound를 pair로 반환. O(logn)

 

Map

int main() {

fastio;

map<int, int> M;

cout << M.count(3) << '\n'; // 0, 즉 3이 없음

M[3]; //[] 연산자를 이용해 M[key] = val과 같이 새 원소를 삽입함

cout << M.count(3) << '\n'; // 1, 즉 3이 생김

}

M[key]를 사용할 땐 새로 원소를 삽입하는게 아니라면 key가 M에 존재하는지 count 등을 이용해 확인해줘야 한다.

set, map에 특정 원소가 존재하는지 여부는 count를 이용하면 된다.

단, multiset, multimap의 count 연산은 O(logn + 원소의 개수)이기 때문에 중복 원소가 많은 경우에는 사용하면 안된다.

 

Set

int main() {

fastio;

set<int> S = { 1, 2, 3 ,4 }; // 초기화

auto it = S.begin(); // *it == 1

advance(it, 3); // *it == 4 오른쪽으로 3칸

advance(it, -2); // *it == 2 왼쪽으로 2칸

it = prev(it); // *it == 1 왼쪽 1칸

it = next(it); // *it == 2 오른쪽 1칸

 

cout << "dist : " << distance(S.begin(), it) << '\n'; // 1

cout << "dist : " << distance(it, S.begin()) << '\n'; // UB 

-> list와 유사

}

 

<List 와 동일한 성질>

set, map의 iterator는 bidirectional iterator이기 때문에 S.begin() + 3 등의 + 연산을 지원하지 않는다. 따라서 it을 이동시키기 위해선 it-- 또는 it++를 이용하거나 prev(it), next(it)을 이용해야 합니다. 만약 여러 칸을 이동해야 한다면 advance를 사용할 수 있다.  이때 advance의 시간복잡도는 O(n)이다

마찬가지로 set, map의 iterator는 iterator간의 - 연산을 지원하지 않아서 it - S.begin() 등으로 인덱스를 구할 수 없다. 이때는 O(n)의 시간복잡도를 갖는 distance를 이용하면 됩니다.

1. set, map에는 front(), back()이 없기 때문에 *S.begin(), *prev(S.end()) 등으로 접근해야 한다.

set, map의 begin(), end()의 시간복잡도는 O(1)이다.

2. set, map의 iterator는 const_iterator이기 때문에 *it = val과 같이 참조를 이용해 직접 수정할 수 없다. 만약 원소를 수정하고 싶다면 set은 삭제 후 삽입을, map은 []연산자를 이용한다.

​3. set, map은 lower_bound, upper_bound를 <algorithm> 헤더의 함수 대신 멤버 함수를 이용한다. 사용 방법은 algorithm 헤더의 함수와 동일하며 lower_bound, upper_bound를 가리키는 iterator를 반환한다.

4. set, map의 erase에 invalid한 iterator를 매개변수로 넣는 것은 UB이다. 즉, iterator는 set, map에 존재하는 원소를 가리키고 있어야 한다. 단, erase(val)처럼 iterator 대신 지울 원소를 넣어주는 경우엔 내부에 val이 없어도 잘 작동한다.

set<int> s = {1, 2, 3, 4, 5};
auto it = s.find(6); // it는 s에 없는 값을 가리키는 iterator
s.erase(it); // 잘못된 iterator를 사용하여 erase -> UB

 

set<int> s = {1, 2, 3, 4, 5};
s.erase(6); // s에 없는 값을 넣어도 잘 작동함

<백준>

1764번)

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

 

 

int main(){

    fastio;

    int p,q;

    cin>>p>>q;

    set<string> S1, S2;

    for (int i=0; i<p; i++){

        string s; cin>>s;

        S1.insert(s);

    }

    for (int i=0; i<q; i++){

        string s; cin>>s;

        if(S1.count(s)) S2.insert(s);

    }

    cout<<S2.size()<<'\n';

    for(const auto&i : S2) cout<<i<<'\n';

}

 

11478번)

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int main(){

    fastio;

    string str;

    cin>>str;

    set <string> S;

    int count=0;

    for (int i=0; i<str.size(); i++) // 모든 시작 가능한 위치

        for(int j=1; j<=str.size()-i; j++) // 만들어질 수 있는 문자열 길이 case

            S.insert(str.substr(i,j)); //i=자르기 시작하는 위치, j=추출할 문자열 갯수

    cout<<S.size()<<'\n';

}

다른 풀이)

int main(){

    fastio;

    string str;

    cin>>str;

    int n = str.size();

    vector <string> v;

    v.reserve(n * (n + 1) >> 1); //미리 v의 용량 확보, i가 0~n-1, j가 1~n-i

    for (int i = 0; i < n; i++)

        for (int j = 1; j <= n - i; j++)

            v.push_back(str.substr(i, j));

    sort(v.begin(), v.end()); //사전 순으로 정렬

    v.erase(unique(v.begin(), v.end()), v.end());

    //unique(): 연속된 중복된 요소를 벡터의 맨 뒤로 이동 + 중복을 제거한 새로운 벡터의 끝 반복자를 반환한다.

   //erase() 함수로 중복이 제거된 범위 이후의 요소들을 제거한다.

    cout << v.size() << '\n';

}

 

1620번)

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int main(){
    fastio;
    int a,b;
    cin>>a>>b;
    map<string, int> name_to_idx;
    map<int, string> idx_to_name;
    
    for (int i=1; i<=a; i++) {
        string str;
        cin>>str;
        name_to_idx[str]=i;
        idx_to_name[i]=str;
    }
    
    while(b--){
        string s; cin>>s;
        if(isdigit(s[0])) cout<<idx_to_name[stoi(s)]<<'\n';
            else cout<<name_to_idx[s]<<'\n';
    }
}

7662번)

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

 

using namespace std;int main(){

    fastio;

    int n; cin>>n;

    while(n--){

        int a; cin>>a;

        multiset<int> MS;

        while(a--){

            char c; int t;

            cin>>c>>t;

            if(c=='D') {

                if(MS.empty()) continue;

                if(t==1) MS.erase(prev(MS.end()));

                else MS.erase(MS.begin());

            }

            else {MS.insert(t);}

        }

        if(MS.empty()) cout<<"EMPTY"<<'\n';

        else cout<<*prev(MS.end())<<' '<<*MS.begin()<<'\n';

    }

}

 

2261번) 가장 가까운 두 점

참고 사이트: https://blogshine.tistory.com/229