[C++] STL set, map (binary search tree) 정리 및 사용법

안녕하세요 기회개발자 기개 입니다.

오늘은 C++에서 binary search tree처럼 사용할 수 있는 set과 map에 대해 소개해보려고 합니다.

 

set과 map의 차이점은 한 가지만 존재하여 같이 다루려고 합니다.

둘의 차이점을 알아보고 binary search tree가 무엇인지, set 과 map의 사용법에 대해 알아봅시다.

 

1. set과 map의 비교

1) 둘 다 binary tree로 구성되어 있다. 일정한 규칙을 가지고 이진트리를 구성한다. 삽입과 삭제를 하면 아래의 규칙에 따라서 알아서 정렬이 된다. 노드의 왼쪽에는 자신보다 우선순위가 작은 것을 놓고, 오른쪽에는 자신보다 우선순위가 높은 것을 놓는다. 2) map은 key와 value로 이뤄지고, set은 key로만 이뤄져있다. map과 set은 둘 다 우선순위를 결정할 유일한 값인 key를 가지고 있다. (key는 중복될 수 없다.) map은 key를 가지지만 key에 매칭이 되는 value(정보)도 넣어줄 수 있다.

 

2. binary search tree 란

1) 삽입 O(log_2​ N) {5, 7, 2, 6, 4, 3} 을 순서대로 넣는다고 하면, 처음에 놓는 5를 root 노드로 배치한다. 7은 5보다 크니 5의 오른쪽에 배치한다. 2는 5보다 작으니 5의 왼쪽에 배치한다. 6은 5보다 크니 5의 오른쪽인 7과 비교를 하면 작으니 7의 왼쪽에 배치한다. 4는 5보다 작으니 5의 왼쪽인 2와 비교를 하면 크니 2의 오른쪽에 배치한다. 3은 5보다 작으니 5의 왼쪽인 2와 비교를 하면 크니 2의 오른쪽인 4와 비교를 하면 작으니 4의 왼쪽에 배치한다. 2) 삭제 O(log_2​ N) ① 자식이 없는 노드 지울 때 그냥 삭제하면 됨 ② 자식노드가 하나인 노드 지울 때 해당 자식노드를 삭제하는 노드의 parent와 연결해주고, 해당 노드를 삭제 ③ 자식노드가 두개인 노드 지울 때 2가지 방법이 있다. 오른쪽 자식 중에 가장 작은 값을 삭제하는 노드 자리로 옮기고 옮긴 노드를 삭제할 때 ①,②,③의 규칙을 따라 다시 진행. 왼쪽 자식 중에 가장 큰 값을 삭제하는 노드 자리로 옮기고 옮긴 노드를 삭제할 때 ①,②,③의 규칙을 따라 다시 진행. 3) 검색 O(log_2​ N) root 노드부터 비교를 진행 찾고자 하는 노드의 우선순위가 비교하는 것보다 작을 경우 왼쪽으로, 클 경우에는 오른쪽으로 이동하며 검색을 진행한다.

 

3. set과 map 사용법 (내장함수)

데이터의 삽입, 삭제, 검색 등을 편하게 하기 위한 내장함수들이 존재합니다.

set과 map은 가지고 있는 내장함수가 동일합니다.

기본적으로 set과 map을 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

#include <set>
#include <map>
#include <string>

using namespace std; // STL을 사용할 때 선언해주면 사용하기 편리합니다.

set<string> s; // key의 자료형 지정
map<string, int> m; // key와 value의 자료형 지정

 

1) 데이터의 삽입

위에서 정리한 binary search tree의 규칙에 맞게 데이터들이 삽입 됩니다.

s.insert("abc");
m.insert({"def", 3});

 

2) 데이터의 삭제

위에서 정리한 binary search tree의 규칙에 맞게 데이터들이 삭제 됩니다.

 

s.erase("abc");
m.erase("def");

 

 

3) 데이터의 접근

set과 map은 binary search tree에 따라 규칙적으로 데이터들이 배치되어 있어 인덱스로도 접근이 가능합니다.

front()와 back()은 없지만 begin()과 end()가 있어서 순회를 할 때 사용할 수도 있습니다.

 

begin() | root 노드를 포인터로 가르킵니다.

s.begin(); // root 노드의 위치를 가르킵니다. *s.begin() == s.front()
m.begin(); // root 노드의 위치를 가르킵니다. *m.begin() == m.front()

end() | 데이터의 끝을 포인터로 가르킵니다.

s.end(); // 데이터의 끝을 가르킵니다. *(s.end() - 1) == s.back()
m.end(); // 데이터의 끝을 가르킵니다. *(m.end() - 1) == m.back()

find() | 찾고자 하는 데이터의 위치를 찾습니다.

auto it = s.find(id);
if(it == s.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

auto it2 = m.find(id);
if(it2 == m.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

 

4) lower_bound, upper_bound (set, map의 핵심)

lower_bound : 찾고자 하는 key 값 이상인 것들 중 가장 작은 key 값을 찾는다.

upper_bound : 찾고자 하는 key 값을 초과하는 것들 중 가장 작은 key 값을 찾는다.

auto it = s.lower_bound(id);
if(it == s.end()) // 찾지 못했을 때 처리
{
	// TODO
}
else // 찾았을 때 처리
{
	// TODO
}

auto it2 = m.upper_bound(id);
if(it2 == s.end()) // 찾지 못했을 때 처리
{
	// TODO
}
else // 찾았을 때 처리
{
	// TODO
}

 

5) 이외에 유용한 내장함수

s.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
s.size(); // 데이터의 갯수 반환
s.clear(); // 초기화 | 결과 {}

 

 

6) 응용

typedef struct st{ // key에 넣을 구조체
    int score;
    int id;
}ST;

struct compare { // 이 기준에 따라 우선순위를 정함
    bool operator()(ST a, ST b) const {
        if(a.score < b.score) return true;
        else if(a.score == b.score && a.id < b.id) return true;
        return false;
    }
};

set<ST, compare> students[GRADE][GENDER]; // 선언

students[mGrade][gender].insert({mScore, mId}); // 삽입

auto it = students[mGrade][gender].end();
--it;
it->id; // 우선순위 가장 낮은 것의 id를 가져옴

students[grade][gender].erase({score, mId}); // 삭제
if(students[grade][gender].empty()) // 비어있을 때 처리

students[grade][gender].begin()->id; // 우선순위 가장 높은 것의 id

auto it2 = students[grade][gender].lower_bound({mScore, -1}); // mScore이상의 score를 가진 것을 가르킴
--it2; // mScore 보다 작은 것 중 가장 큰 것을 가르키게 됨.