백준/이론_C++

SET 자료구조 사용법 C++

휴대용치즈 2023. 4. 16. 23:09

SET


C++의 set은 STL(Standard Template Library)의 컨테이너 중 하나로, 중복된 값을 저장하지 않는 정렬된 자료구조입니다.

set은 이진 탐색 트리(binary search tree)를 기반으로 구현되어 있으며, 값 삽입, 삭제, 검색 등의 연산에 높은 성능을 보입니다.

 


set은 다음과 같은 특징을 가집니다:
1. 중복된 값을 허용하지 않습니다.
2. 값이 항상 정렬된 상태를 유지합니다. (기본적으로 오름차순 정렬)
3. 값 삽입, 삭제, 검색 등의 연산에 대해 빠른 속도를 보입니다.
4. 값이 삽입되면 자동으로 정렬되므로, 삽입 후에도 정렬을 할 필요가 없습니다.

 


set의 시간복잡도는 다음과 같습니다:
값 삽입: O(log n)
값 삭제: O(log n)
값 검색: O(log n)

 

 

set을 사용하기 위해서는 다음과 같이 헤더 파일 을 include해야 합니다:

#include <set>

 

 

SET 함수


insert()

set에 새로운 요소를 추가합니다.

std::set<int> s;
s.insert(1);



emplace()

set에 새로운 요소를 추가합니다.

insert()와 다르게, 객체를 복사하지 않고 바로 set 내부에서 생성합니다.

std::set<std::string> s;
s.emplace("hello");

 


erase()

set에서 특정 요소를 제거합니다.

std::set<int> s{1, 2, 3};
s.erase(2);



clear()

set의 모든 요소를 제거합니다.

std::set<int> s{1, 2, 3};
s.clear();



find()

set에서 특정 값에 대한 반복자(iterator)를 반환합니다.

해당 값이 set에 없으면 set::end()를 반환합니다.

std::set<int> s{1, 2, 3};
std::set<int>::iterator it = s.find(2);
if (it != s.end()) {
  // 값이 있음
} else {
  // 값이 없음
}



count()

set에서 특정 값이 몇 개 있는지 반환합니다.

set에서는 중복된 값을 허용하지 않기 때문에, 해당 값이 존재하지 않으면 0을 반환합니다.

std::set<int> s{1, 2, 2, 3};
int cnt = s.count(2); // 2가 두 개 있으므로 cnt는 1이 됩니다.



size()

set의 요소 개수를 반환합니다.

std::set<int> s{1, 2, 3};
int cnt = s.size(); // cnt는 3이 됩니다.