template<
class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>
> class set;
set은 집합을 구현한 컨테이너이다. <set> 헤더에서 구현한다. 내부적으로 이진 탐색 트리를 이용해 대부분의 연산은 O(lgN)이다.
1. 사용
set은 중복값 제거, 두 데이터간 일치하는 데이터 찾기, 특정 요소 탐색 등에 주로 사용된다. 탐색 트리로 정렬된 순서를 보장하기 때문에 관련 연산에서도 사용할 수 있다. 또, 균형 트리를 사용하기 때문에 이진 트리와 관련된 연산을 사용하고자 할 때 사용하기도 한다.
생성
다양한 방법을 이용해 생성 가능하다. 빈 컨테이너를 생성하거나, 미리 요소가 추가된 컨테이너를 생성할 수 있다. 각 생성자들은 Allocator를 추가적으로 받을 수 있다. 모든 삽입 연산은 O(lgN)이기 때문에 N개의 요소를 동시에 생성하는 생성자는 O(NlgN)의 실행시간을 갖는다.
- 기본 생성자
- initializer_list를 전달하는 생성자
- 시작과 끝의 이터레이터를 전달하는 생성자
- 복사 생성자
- 이동 생성자
// 1. 기본 생성자
// 아무것도 할당되지 않은 상태로 초기화.
set<int> s1;
// 2. initializer_list
set<int> s2 = { 1,2,3,4,5 }; // 1 2 3 4 5
set<int> s2_2{ 1,2,3,4,5 };
set<int> s2_3({ 1,2,3,4,5 });
// 3. iterator
set<int> s3(s2.begin(), s2.end()); // 1 2 3 4 5;
// 4. copy
set<int> s4(s3); // 1 2 3 4 5
// 5. move
set<int> s5(move(s4)); // 1 2 3 4 5
추가적으로 compare 함수를 전달할 수 있다. compare는 컨테이너가 내부에서 요소간 비교를 수행할 때, 그 연산을 수행하는 함수이다. 이는 삽입, 검색 등 다양한 곳에 이용된다. comp를 전달하지 않은 set은 기본적으로 오름차순 관계를 갖는다. std에서는 기본적인 compare 함수를 제공하는데, 오름차순으로 정렬되는 std::less<Ty>()와 내림차순으로 정렬되는 std::greater<Ty>()가 있다. compare를 전달하지 않으면 기본적으로 std::less<>가 전달된다.
// 6. comp 전달
// 내림차순으로 정렬됨.
set<int> s6(greater<int>());
set<int, greater<int>> s6_2;
// 7. comp with initializer_list
set<int, greater<int>> s7({ 1,2,3,4,5 }); // 5 4 3 2 1
// 8. iterator
set<int, greater<int>> s8(s7.begin(), s7.end()); // 5 4 3 2 1
// 9. copy
set<int, greater<int>> s9(s7); // 5 4 3 2 1
// 10. move
set<int, greater<int>> s10(move(s9)); // 5 4 3 2 1
greater와 less는 괄호 연산자가 로버로딩된 구조체이다. 필요에 따라서 직접 정의할 수도 있다.
template <class _Ty = void>
struct Greater {
bool operator()(_Ty& _Left, _Ty& _Right) {
return _Left > _Right;
}
};
template <class _Ty = void>
struct Less {
bool operator()(_Ty& _Left, _Ty& _Right) {
return _Left < _Right;
}
};
이를 구조체가 아닌 일반 함수로 만들어 사용할 수도 있다.
template<typename Ty>
bool greaterFunc(Ty& left, Ty& right) {
return left > right;
}
// 템플릿을 사용하지 않는 경우
bool lessIntFunc(int& left, int& right) {
return left < right;
}
접근
집합 요소에 접근하겠다는 소리는 트리에서 특정한 값을 검색하겠다는 소리이다. 따라서, O(1)으로 요소에 접근할 수 있는 직접적인 연산은 지원하지 않는다. 요소에 직접 접근하기 위해서는 이터레이터를 이용하거나, 조회 연산을 이용해야 한다.
이터레이터
역참조로 얻을 수 있는 참조값 (*iter)를 읽을 수는 있지만, 수정할 수는 없다. 그 외에 ++, – 정도의 연산을 지원한다. 이터레이터는 트리를 inorder로 순회하는 관계를 갖기 때문에 이터레이터를 순회하면 정렬된 순서가 보장된다.
용량
size- 현재 보관 중인 요소의 개수max_size- 저장 가능한 최대 요소의 개수 (컴퓨터의 전체 가용 메모리)empty- 요소가 비어있는지 확인한다.
set<int> s{ 1,2,3,4,5 };
s.size(); // 5
s.empty(); // false
s.max_size(); // 메모리의 총량
수정
insert()와 emplace()로 요소를 삽입하고, erase()로 요소를 삭제한다. comp와 트리의 구조에 따라 요소의 위치가 결정되기 때문에 삽입 위치를 직접 설정할 수 없다. 모든 삽입과 삭제는 O(lgN)으로 일어난다.
set<int> s{ 3,8,11 };
s.insert(5); // 3 5 8 11
s.emplace(6); // 3 5 6 8 11
s.emplace(3); // 이미 존재하기 때문에 아무 일도 일어나지 않는다.
s.erase(3); // 5 6 8 11
s.erase(3); // 3은 존재하지 않기 때문에 아무 일도 일어나지 않는다.
merge()를 이용해서 두 set을 하나로 합칠 수 있다. 매개변수로 들어오는 set은 복사가 아니라 이동된다. clear()함수로 컨테이너를 비울 수 있다.
set<int> s1{ 1,3,5,7 };
set<int> s2{ 2,4,6,8 };
s1.merge(s2); // 1 2 3 4 5 6 7 8
s1.clear(); // empty
extract는 set에서 요소를 제거하면서 제거된 요소의 tree_node를 반환한다. 반환된 node에는 요소의 값은 물론 기존 연결되어 있었던 부모, 자식에게도 접근할 수 있다.
// 4
// 2 5
// 1 3
set<int> s{ 1,2,3,4,5 };
auto v1 = s.extract(1); // node_handle
auto v2 = v1._Getptr()->_Parent; // value_type
cout << v1.value() << endl; // 1
cout << v2->_Left->_Myval << endl; // 1이 tree에서 삭제되어 쓰레기 값 출력
cout << v2->_Right->_Myval << endl; // 3
조회
set의 핵심 기능은 값의 존재 여부를 검색하고, 중복을 제거하는 것이다. 이러한 연산을 조회(Lookup)이라고 한다. 이중 equal_range는 set보다는 multiset을 위한 연산이라고 생각하는게 좋다.
count(v)- 보관된 v의 개수를 반환한다.find(v)- v가 존재하면 v의 이터레이터를, 아니면 past-the-end 이터레이터를 반환한다.contains(v)- v가 존재하면 true를 반환한다.equal_range(v)- v값이 존재하는 범위를 이터레이터 2개로 반환한다.lower_bound(v)- v 값이나 없다면 v에 가장 가까운 오른쪽 값을 반환한다.upper_bound(v)- v과 가장 가까운 오른쪽 값을 반환한다.
lower_bound()와 upper_bound()는 past-the-end를 반환할 수 있다는 점에서 항상 주의해야 한다. 오름차순을 기준으로 lower_bound는 v가 존재하면 v를 아니면 v보다 큰 수 중 가장 작은 수를 반환한다. upper_bound는 항상 v보다 크면서 가장 작은 수를 반환한다.
set<int> s{ 1,2,3, 3,7,9 };
cout << s.count(3) << endl; // 1
auto iter = s.find(3);
for (auto iter = s.find(3); iter != s.end(); iter++) {
cout << *iter << ' '; // 3 7 9
}
cout << endl;
if (s.find(5) == s.end()) {
cout << "5은 존재하지 않음." << endl;
}
cout << (s.contains(1)) << endl; // 1
cout << (s.contains(5)) << endl; // 0
auto [begin, end] = s.equal_range(3); // 3~7
for (auto iter = begin; iter != end; iter++) {
cout << *iter << ' '; // 3
}
cout << endl << endl;
cout << "i\tlower\tupper" << endl;
for (int i = 0; i <= 10; i++) {
cout << i << '\t';
auto lower = s.lower_bound(i);
if (lower == s.end()) {
cout << "end\t";
}
else {
cout << *lower << '\t';
}
auto upper = s.upper_bound(i);
if (upper == s.end()) {
cout << "end" << endl;
}
else {
cout << *upper << endl;
}
}
1
3 7 9
5은 존재하지 않음.
1
0
3
i lower upper
0 1 1
1 1 2
2 2 3
3 3 7
4 7 7
5 7 7
6 7 7
7 7 9
8 9 9
9 9 end
10 end end
2. multiset
multiset은 중복을 포함한다는 점을 제외 하고는 set과 동일하다. 그러나, 그 차이 하나로 여러 연산에서 다른 결과를 볼 수 있다. multiset은 <set> 헤더에 구현되어 있다.
우선 count()를 더 의미있게 사용할 수 있다. set에서는 0아니면 1이었기 때문에 find나 contains를 사용하는 것과 다를게 없었지만, multiset에서는 같은 요소가 여러 번 저장될 수 있기 때문에 보관된 요소의 수를 출력한다.
equal_range()역시 set에 비해서 의미있게 사용할 수 있다. 해당 메서드를 사용해서 중복되는 모든 요소의 이터레이터를 얻을 수 있다.
multiset<int> ms{ 1,2,2,2,3,3 }; // 1 2 2 2 3 3
ms.count(1); // 2
auto [begin, end] = ms.equal_range(2); // 1번 iter ~ 4번 iter
for (auto iter = begin; iter != end; iter++) {
cout << *iter << ' '; // 2 2 2
}
find()의 경우에는 가장 왼쪽에 있는 요소의 이터레이터를 반환한다. lower_bound와 upper_bound 역시 연산을 만족하는 가장 왼편의 값을 반환한다.
for (auto iter = ms.find(2); iter != ms.end(); iter++) {
cout << *iter << ' '; // 2 2 2 3 3
}
cout << endl;
// 가장 왼편의 2를 선택함
for (auto iter = ms.lower_bound(2); iter != ms.end(); iter++) {
cout << *iter << ' '; // 2 2 2 3 3
}
cout << endl;
// 가장 왼편의 3을 선택함.
for (auto iter = ms.upper_bound(2); iter != ms.end(); iter++) {
cout << *iter << ' '; // 3 3
}
cout << endl;
2 2 2 3 3
2 2 2 3 3
3 3