[C++] Day 7 - 자료 구조(3) - 집합 자료 구조

오늘은 집합 자료 구조에 대해 배운다.

파이썬에서는 보통 set을 이용해서 집합을 만들고, in을 이용해서 O(1) 안에 원소가 있는지 없는지 찾을 수 있었다.

C++에서는 어떻게 할까?

 

셋과 멀티셋

C++ 표준 라이브러리에는 경진 프로그래밍에서 자주 쓰는 집합 자료 구조가 두 개 있다.

 

set

균형 잡힌 이진 탐색 트리를 기반으로 만들어졌으며, 연산은 O(log n) 시간에 동작한다.

 

unordered_set

해시 테이블을 기반으로 만들어졌으며(python 에서 set과 비슷), 연산은 평균적으로(최악의 경우 O(N)) O(1)에 동작한다.

 

위 둘 다 중복된 원소는 허용하지 않는다.

 

둘 다 사용법은 비슷하니 set를 통해 예시를 보도록 하겠다.

 

set<int> s;

s.insert(3);
s.insert(2);
s.insert(5);

cout << s.count(3) << '\n'; // 1
cout << s.count(4) << '\n'; // 0

s.erase(3);

 

인덱싱은 불가능 하다.

 

find 함수는 값이 x인 원소를 가리키는 반복자를 반환한다. 그러한 원소가 없으면 end()를 반환한다.

 

auto it = s.find(x);
if (it == s.end()) {
	// 없다
}

 

 

set은 unordered_set과 다르게 정렬된 집합이다. 그래서 집합에서 가장 큰 원소과 가장 작은 원소를 다음과 같이 얻을 수 있다.

 

auto first = s.begin();
auto last = s.end(); last--; //last는 마지막 원소 위치 다음 값을 가리키기 때문.
cout << *first << " " << *last << '\n';

 

set에는 lower_bound(x)와 upper_bound(x) 함수도 있는데, 각각은 값이 x 이상인 첫 번째 원소와 x보다 큰 첫 번째 원소의 반복자를 반환한다. 두 함수 모두 그러한 원소가 없을 때는 end()를 반환한다.

 

만약 정렬 순서를 반대로 하고 싶다면 이렇게 하면 된다.

 

set<string, greater<string>> s;

 

이게 되는 이유는, 사실 두 번째 인자가 비교(compare)인자 이기 때문이다.

multiset과 unordered_multiset

멀티셋은 같은 값을 여러 개 가질 수 있다. 나머지는 거의 같다.

 

다만, 다음 코드는 멀티셋의 특정 값을 모두 삭제한다.

s.erase(5);

 

원소중에 하나만을 삭제하려면 다음과 같이 한다.

 

s.erase(s.find(5));

 

 

맵

C++에서의 맵은 파이썬에서의 딕셔너리다.

마찬가지로 그냥 map과 unordered_map이 있다.

 

map<string, int> m;
m["apple"] = 3;
m["banana"] = 4;
m["ipad"] = 5;

cout << m["ipad"]; // 5

 

특정 키의 값을 요청했는데 맵에 그 키가 없으면, 키가 자동으로 생성되며 값은 기본값으로 설정된다.

 

어떤 키가 있는지 확인하려면 count를 써주면 된다.

 

if (m.count("apple")) {
	//what
}

 

다음 코드는 맵에 저장된 모든 키와 값을 출력한다.

 

for (auto x : m) {
  cout << x.first << " " << x.second << '\n';
}

 

 

 

우선순위 큐

우선순위 큐는 원소의 추가, 탐색, 그리고 삭제 연산이 있는 멀티셋이다. 이때 탐색 및 삭제의 대상이 되는 원소는 최소, 또는 최대 원소이며, 둘 중 어느 쪽이 대상이 되는지는 큐의 속성에 달려있다. 원소의 추가, 삭제는 O(log n)시간이 걸리며, 탐색은 O(1)이 걸리는 아주 자주 쓰는 개꿀 자료구조이다. 힙을 기반으로 만들어졌다. 

 

파이썬에서는 리스트를 heap으로 만들어서 쓰는 방식이었지만 C++에서는 자료구조가 아예 따로 있다.

 

기본적으로는 원소가 내림차순으로 정렬되어있다. 즉, 탐색 및 삭제의 대상이 되는 것은 최대 원소이다.

 

priority_queue<int> a;
a.push(3);
a.push(3);
a.push(5);
a.push(2);
cout << a.top() << ' ';
a.pop();
cout << a.top() << ' ';
a.pop();
a.push(6);
cout << a.top() << ' ';

// 5 3 6

 

만약 이걸 파이썬마냥 최소 원소에 대해 하고 싶다면 다음과 같은 방법을 쓰면 된다.

 

1. 저장할 때 음수를 저장한다. (파이썬에서 주로 썼던 방법)

2. 다음과 같이 한다.

priority_queue<int, vector<int>, greater<int>> a; //아예 자료구조를 이렇게 만들어버린다

 

 

 

실행 시간?

보통 unordered가 붙은 것이 그렇지 않은 것보다 더 빠르며,

우선순위 큐가 멀티셋보다 더 빠르다.