[자료구조] C++ STL(Container): set, map, multiset, multimap, hash

C++ 표준 라이브러리(STL)에서 제공하는 set, map, multiset, multimap 등의 컨테이너와 해시 기반 컨테이너에 대해 소개하겠습니다.

 

연관 컨테이너(Associative Containers)

정해진 정렬 기준에 따라 정렬된 자료구조를 의미합니다.

이 컨테이너들은 Red-Black Tree 기반으로 구현되며, 모든 요소는 정렬된 상태를 유지합니다. 자가 균형 이진 트리를 사용하므로 삽입, 삭제, 조회에 O(log n)의 시간 복잡도를 가집니다.

레드-블랙 트리 (red-black tree)는 자가 균형 이진 탐색 트리 (self-balancing binary search tree)로서, 대표적으로는 
연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

레드 블랙 트리 예

---

Set, Multiset

기본 구조

• set: 중복을 허용하지 않는 정렬된 컨테이너.
• multiset: 중복된 값을 허용하는 정렬된 컨테이너.

주요 연산과 시간 복잡도

삽입(insert)	O(log n)
삭제(erase)	O(log n)
검색(find)	O(log n)
이터레이터 사용	정렬 순서 유지

 

예시 코드

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> mySet;
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(20);

    // 중복 허용 X
    mySet.insert(10);

    // 출력 (정렬된 순서)
    for (int x : mySet) {
        cout << x << " ";
    }
    cout << '\n';

    // multiset 예시
    multiset<int> myMultiSet;
    myMultiSet.insert(10);
    myMultiSet.insert(10);
    myMultiSet.insert(20);

    // 출력 (중복 포함)
    for (int x : myMultiSet) {
        cout << x << " ";
    }
    return 0;
}

출력 결과

---

Map과 Multimap

기본 구조

• map: 키-값 쌍을 저장하며, 키는 고유해야 함.
• multimap: 키가 중복될 수 있는 정렬된 키-값 쌍.

 

주요 연산과 시간 복잡도

삽입(insert)	O(log n)
삭제(erase)	O(log n)
검색(find)	O(log n)
이터레이터 사용	키 순서 유지

 

예시 코드

 

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";

    // 출력 (정렬된 키 순서)
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << '\n';
    }

    // multimap 예시
    multimap<int, string> myMultiMap;
    myMultiMap.insert({ 1, "One" });
    myMultiMap.insert({ 1, "Uno" });
    myMultiMap.insert({ 2, "Two" });

    // 출력 (중복 키 포함)
    for (const auto& pair : myMultiMap) {
        cout << pair.first << ": " << pair.second << '\n';
    }
    return 0;
}

출력 결과

---

비정렬 연관 컨테이너(Unordered Associative Containers)

해시를 사용해서 데이터를 저장하는 자료구조입니다.

대부분의 경우에 삽입, 삭제, 조회에 O(1)로 해시 충돌이 일어나지 않은 경우 연관 컨테이너보다 효율적이지만, 충돌한 요소에서는 버킷(연결리스트)의 크기만큼 시간이 더 걸립니다. 이는 체이닝이란 해시 충돌 해결 기법을 사용했기 때문입니다.

 

해시 테이블 체이닝 예시

unordered_set, unordered_map, unordered_multiset, unordered_multimap이 있고, 정렬이 되어있지 않을 뿐 연관 컨테이너와 용도와 사용 방법은 동일합니다.

---

Unordered_Set, Unordered_Map, Unordered_Multiset, Unordered_Multimap

주요 연산과 시간 복잡도

삽입(insert)	O(1)	O(n)
삭제(erase)	O(1)	O(n)
검색(find)	O(1)	O(n)
이터레이터 사용	삽입 순서와 무관

 

예시 코드

#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main() {
    // unordered_set
    unordered_set<int> myUnorderedSet = { 10, 20, 30 };
    myUnorderedSet.insert(40);
    myUnorderedSet.insert(20);
    myUnorderedSet.insert(30);
    myUnorderedSet.insert(30);

    for (int x : myUnorderedSet) {
        cout << x << " ";
    }
    cout << '\n';

    // unoredered_multiset
    unordered_multiset<int> myUnorderedMultiSet = { 10, 20, 20, 30 };
    myUnorderedMultiSet.insert(40);
    myUnorderedMultiSet.insert(20);
    myUnorderedMultiSet.insert(30);
    myUnorderedMultiSet.insert(30);

    for (int x : myUnorderedMultiSet) {
        cout << x << " ";
    }
    cout << '\n';

    // unordered_map
    unordered_map<int, string> myUnorderedMap;
    myUnorderedMap.insert({ 1, "One" });
    myUnorderedMap.insert({ 3, "Three" });
    myUnorderedMap.insert({ 2, "Two" });
    myUnorderedMap.insert({ 2, "Twooo" });

    for (const auto& pair : myUnorderedMap) {
        cout << pair.first << ": " << pair.second << '\n';
    }
    cout << '\n';

    // unordered_multimap
    unordered_multimap<int, string> myUnorderedMultiMap;
    myUnorderedMultiMap.insert({ 1, "One" });
    myUnorderedMultiMap.insert({ 3, "Three" });
    myUnorderedMultiMap.insert({ 2, "Two" });
    myUnorderedMultiMap.insert({ 2, "Twooo" });

    for (const auto& pair : myUnorderedMultiMap) {
        cout << pair.first << ": " << pair.second << '\n';
    }
    cout << '\n';

    return 0;
}

결과 출력

---

정리

STL의 사용법을 잘 알고 있으면 매우 유용합니다. 데이터를 정렬된 상태로 유지해야 하는지와 해시 충돌과 속도 등을 고려하여 적절히 연관 컨테이너와 비정렬 연관 컨테이너를 사용하길 바랍니다.

 

추천 문제

https://www.acmicpc.net/problem/1620

https://www.acmicpc.net/problem/14425

https://www.acmicpc.net/problem/21939

https://www.acmicpc.net/source/84226926