C++: set 사용하기

set이란?

set은 하나의 항목만을 갖게 하는 집합 자료구조 입니다. 

예를들어 (아래는 Python 문법)

alist = [0, 1, 2, 2, 2, 1, 0]  와 같은 리스트가 있다면, 이를 set으로 바꿀 시 다음과 같이 중복이 제거됩니다. 

alist = list(set(alist))

# alist has [0, 1, 2]

 

C++의 set

C++에서도 set을 지원하며, 2가지 형태의 set을 지원합니다. 

set과 unordered_set 입니다. 

각각 set은 tree를 unordered_set은 hash를 사용합니다. 

즉, set은 원소를 찾는데 걸리는 시간이 O(NlogN)이며 unordered_set은 O(1) 입니다. 

그러나 원소가 매우 많아질 경우 unordered_map의 경우 hash bucket의 충돌이 발생하게 적절한 튜닝을 하지 않을 경우 성능이 나빠질 수 있습니다. 

 

사용 방법

일단, set을 include 합니다.

#include <set>

int type을 갖는 set을 선언하고, 여기에 int 값들을 대입해 보겠습니다. 

int alist[] = {1, 2, 2, 2, 1, 3};
std::set<int> iset{alist, alist + sizeof(alist)/sizeof(alist[0])};

이제 set의 원소들을 출력해 보겠습니다. 

for (auto itor = iset.begin(); itor != iset.end(); itor++) {
    std::cout<<*itor<<std::endl;
}

1, 2, 3을 출력합니다. 

 

값의 존재 여부 확인은 find로 수행합니다. 

auto itor = iset.find(5);
if (itor != iset.end()) {
    std::cout<<"found!"<<std::endl;
}

5는 존재하지 않으므로 찾지 못합니다. 

이외에 값이 비었는지 비어있지 않은지를 확인하는 empty()와 모든 원소를 제거하는 clear()가 있습니다. 

 

원소의 제거는 erase로 수행합니다. 

// 값을 찾아서 제거
auto itor = iset.find(1);
if (itor != iset.end())
	iset.erase(itor);
    
iset.erase(1);    // 값으로 바로 제거를 시도할 수 있으며, 이 경우 이미 삭제된 원소이므로 아무 행동을 수행하지 않음

 

Custom class 사용

class Point {
public:
	int x, y;
    
    Point(const int &a, const int &b) :
    	x(a), y(b) {
    }
    
    inline bool operator<(const Point &other) const {
    	return uthis->x < other.x;    
    }
};

set객체에 class를 사용하려면 위와 같이 비교 연산자가 정의되어 있어야 합니다. 

 

다음과 set을 선언하고 같이 값들을 넣을 수 있습니다.

std::set<Point> pset;

pset.insert(0, 0);   // 임시 객체를 생성하고 복사하여 추가
pset.emplace(1, 2);  // 임시 객체를 생성하고 move copy 하여 추가
ps.insert(Point(3, 4));

 

값의 순회

for (auto itor = pset.begin(); itor != pset.end(); ++itor) {
    std::cout << (*itor).x << ", " << itor->y << std::endl;
}

// 혹은

for (auto &item : pset) {
    std::cout << item.x << ", " << item.y << std::endl;
}

 

값의 존재 확인

if (pset.find(Point(0, 0)) != pset.end()) {
    std::cout << "found" << std::endl;
}