서론
set의 특징
셋은 자료를 담을 수 있는 컨테이너다. 그러나 벡터, 리스트 등 시퀀스 컨테이너와는 다르게 원소의 삽입순서에 의미를 두지 않는다. 일단 셋에 원소가 삽입되면 자동으로 오름차순이나 내림차순으로 정렬된다. 따라서 삽입순서가 필요하다면 사용해서는 안된다.
셋의 가장 큰 특징은 중복값을 허용하지 않는 것이다. 셋에 1을 10번 넣으면 첫 한번만 들어가고 나머지는 버려진다.
셋에 원소가 들어가면 그 원소의 값을 키(key)라고 한다. 셋은 중복원소를 허용하지 않기 때문에 각 키는 전부 고유하다. 이 글에서는 키를 원소라고 부를것이다. 원소라고 불러도 크게 혼동의 여지가 없으며 서론을 읽지 않는 분들을 위해서다.
set은 언제 사용하면 좋을까
- 삽입과 동시에 정렬이 필요할 때
- 중복을 제거한 원소의 집합이 필요할 때
- 현재 원소가 중복된 값인지 확인이 필요할 때
시간복잡도
셋은 Balanced Binary Search Tree로 구현되어 있어서 검색은 O(logn), 삽입과 삭제는 O(logn+a)이다. a는 트리 재배열인데, 이때문에 삽입과 삭제는 대략적으로 O(nlogn) ~ O(n) 까지 가는것으로 알고 있다.
트리재배열의 시간복잡도가 부정확할 수 있습니다. 혹시 정확하게 알고 계시는분이 있으시면 댓글로 남겨주시면 감사하겠습니다.
set과 unorded_set
unorded_set은 C++11부터 사용할 수 있다. 이름 그대로 set이지만 정렬이 되지 않는다.
| set | unorded_set | |
|---|---|---|
| 구현 방법 | 트리 | 해시 테이블 |
| 정렬 유무 | 정렬 | 비정렬 |
| 멤버 함수 | binary_search(), lower_bound(), upper_bound() 사용 가능 | binary_search(), lower_bound(), upper_bound() 사용 불가 |
| 시간복잡도 | 검색 : O(logn) 삽입, 삭제 : O(logn + a) | 검색, 삽입, 삭제 : O(1) ~ O(n) |
set과 unorded_set 시간복잡도 분석
https://medium.com/@gx578007/searching-vector-set-and-unordered-set-6649d1aa7752
헤더파일
셋은 set 클래스 내부에 있다. 네임스페이스는 std를 사용한다.
#include <set> using namespace std;
셋 선언
set<자료형, 정렬방식>이름;자료형은 int, string 등이 들어갈 수 있다.
정렬방식은 내림차순과 오름차순이 있으며 생략시 오름차순이 기본으로 설정된다.
set<string>s; // 오름차순 set<string, greater<>>s; // 내림차순
멤버함수
알고리즘 문제풀이에 자주 사용되는 멤버함수이다. 모든 멤버함수는 아래 링크를 참조한다.
https://docs.microsoft.com/en-us/cpp/standard-library/set-class?view=vs-2019
insert(원소)셋에 원소를 삽입한다.
set<string>s;
s.insert("a"); // s={a}
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
리턴값은 pair이며 pair의 first는 iterator, second는 insert 성공유무다.
set<string>s;
std::pair<set<string>::iterator,bool> ret;
ret = s.insert("a"); // s={a}
cout<< ret.second <<endl; // 출력 : 1
ret = s.insert("a"); // s={a}
cout<< ret.second <<endl; // 출력 : 0, a가 이미 set에 있음
ret = s.insert("b"); // s={a, b}
cout<< ret.second <<endl; // 출력 : 1
erase(원소)셋에서 원소를 제거한다.
set<string>s;
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
s.erase("a"); // s={b}
파라미터를 원소 대신 iterator를 넣어서 제거할 수도 있다. iterator를 리턴값으로 가지는 find() 함수를 이용하면 되지만 위와 같이 원소를 바로 넣는게 더 편하다.
set<string>s;
set<string>::iterator iter;
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
s.erase(s.find("a")); // s={b}
erase(first iterator, end iterator)으로 구간을 지울 수 있다. 구간을 지울 때는 find()가 편리하게 사용될 수 있다.
set<int>s;
for(int i=0;i<10;i++) s.insert(i*10); // s={0,10,20,30,40,50,60,70,80,90}
s.erase(s.find(30), s.find(70)); // s={0,10,20,70,80,90}
lower_bound(값), upper_bound(값)lower_bound는 값보다 크거나 같은 가장작은 원소의 iterator를 리턴하고 upper_bound는 값보다 큰 가장작은 원소의 iterator를 리턴한다.
erase()와 활용하여 특정 범위를 지울 수 있는데, find()와 다르게 원소가 아닌 값을 입력해도 된다.
set<int>s;
set<int>::iterator l, u;
for(int i=0;i<10;i++) s.insert(i*10); // s={0,10,20,30,40,50,60,70,80,90}
l = s.lower_bound(12);
u = s.upper_bound(78);
s.erase(l, u); // s={0,10,80,90}
begin(), end()셋의 시작 iterator와 끝 iterator를 리턴한다.
set<string>s;
set<string>::iterator iter;
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
s.insert("c"); // s={a, b, c}
iter = s.begin();
cout<<*iter<<endl; // 출력 : a
iter = s.end();
cout<<*iter<<endl; // 출력 : NULL
begin과 end를 각자 사용하는것은 활용도가 떨어진다. begin은 시작 원소라도 알 수 있는데 end는 그것마저도 안된다.
begin과 end는 for문에서 같이 사용하여 set의 원소들을 나열할때 활용한다.
set<string>s;
set<string>::iterator iter;
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
s.insert("c"); // s={a, b, c}
for(iter = s.begin(); iter != s.end(); iter++) cout<<*iter<<" "; // 출력 : a b c
C++11에서는 iterator없이 range-based for loop를 통해 쉽게 출력 가능하다.
count(원소)셋에 원소가 있으면 1, 없으면 0을 리턴한다. 많이 활용되는 함수.
set<string>s;
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
cout<<s.count("b"); // 출력 : 1
cout<<s.count("e"); // 출력 : 0
clear()셋의 모든 원소를 지운다.
set<string>s;
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
s.clear(); // s={}
size(), empty()size는 원소의 개수를 반환하고 empty는 원소가 있으면 0, 없으면 1을 반환한다.
set<string>s;
s.insert("a"); // s={a}
s.insert("b"); // s={a, b}
s.insert("c"); // s={a, b, c}
cout<<s.size(); // 출력 : 3
cout<<s.empty(); // 출력 : 0
예제 코드
중복을 제거한 집합 만들기
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main(){
vector<int>v = {9,7,2,3,4,2,2,4,8,1,9};
set<int>s;
pair<set<int>::iterator,bool> ret;
for(auto i : v) {
ret = s.insert(i);
if(ret.second == 0) cout<< "중복된 값 : "<<i<<endl;
}
cout<<"set : ";
for(auto i : s) cout<<i<<" ";
}
참고
www.geeksforgeeks.org/set-vs-unordered_set-c-stl
www.geeksforgeeks.org/unordered_set-in-cpp-stl
www.docs.microsoft.com/en-us/cpp/standard-library/set-class?view=vs-2019
www.medium.com/@gx578007/searching-vector-set-and-unordered-set-6649d1aa7752