[C++ STL] std::set을 통한 중복 제거 (Duplicate 판단 기준)

이전 글

[STL] Set, Map Custom Sort 구현 방법 (Red-black tree)

 

이전 글에서 Set을 이용한 Custom Sort 구현 방법에 대해서 소개하였다. 윗 포스터와 같이 std::set은 Balanced Binary Tree (i.e. Red-Black Tree)를 기반으로 구현[1]되었기에 내부적으로 데이터들을 정렬하여 저장한다. 따라서 std::set을 정렬을 위한 용도로 사용할 수 있다.

 

 

 

std::set의 또다른 기능 : Duplicate 테스트 및 중복 제거

std::set은 정렬 용도 말고도 중복된 요소 제거를 위해 사용될 수 있다. 이는 Set 자료구조의 기본 특성인, std::set 내 저장된 데이터는 고유의 Key 값을 가져야 한다는 특성[2] 덕분이다. 즉 std::set 내 모든 데이터는 유일해야 하며 중복을 허용하지 않는다.

 

std::vector<int> vec;
... Do something

// no_dupl은 중복된 값을 가지지 않는다.
std::set<int> no_dupl( vec.begin(), vec.end() ); 

// 다시 no_dupl의 값을 vec에 저장한다.
vec.assign( s.begin(), s.end() );

 

위 코드는 std::vector 내의 중복된 값을 std::set을 이용해 제거하는 간단한 코드이다. 단 두 줄이면 (vector -> set 변환, set -> vector 변환) std::vector 내에 저장된 중복된 요소들을 모두 제거할 수 있다.

 

 

 

 

std::set의 duplicate 판단 기준

std::set은 내부적으로 정렬된 자료구조로 데이터를 저장하기에, 데이터 저장 시 데이터간 비교 연산자를 이용해 대소관계를 비교한다. 그렇다면 어떻게 두 데이터가 같은 지 (equivalent) 를 판단할까?

 

std::set은 데이터 a, b가 

!comp(a, b) && !comp(b, a).

 

위 식을 만족할 때, 두 데이터 a, b가 동일하다고 판단[1][3]한다. 

 

따라서 Custom Sort를 개발할 시, 비교 연산자 opeartor< 만 정의해주면 되고, 비교 연산자 operator==는 정의해 줄 필요가 없다.

 

 

 

Reference

[1] https://en.cppreference.com/w/cpp/container/set

[2] https://learn.microsoft.com/ko-kr/cpp/standard-library/set-class?view=msvc-170

[3] https://stackoverflow.com/questions/1114856/stdset-with-user-defined-type-how-to-ensure-no-duplicates