[C++] set, multiset 클래스 정리
🦥 set?
1) Associative Container
set은 연관 컨테이너, 즉 빠르게 검색할 수 있는 노드 기반 이진 트리 구조이다.
2) 중복 허용 안함 (unique)
set은 원소를 값으로 식별하기 때문에 (key가 value) 모든 값은 유일해야 한다. 또한 값의 수정이 불가능하기 때문에 수정을 하기 위해서는 값을 삭제하고 새로운 원소를 추가해야 한다.
3) 삽입과 동시에 정렬 (always sorted)
template <
class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T>, // set::allocator_type
> class set;
위의 Compare 필드에 정의되는 함수를 기준으로 정렬한다. 그래서 데이터가 많고 검색을 자주하는 경우 set을 사용하면 좋다. 그리고 정렬된 구조이기 때문에 검색, 삽입, 삭제가 빠르다(모두 O(logn)). Compare 클래스 default는 less
▶ 참고. Red-Black Tree (자가 균형 이진 탐색 트리)?
set은 Red-Black Tree(자가 균형 이진 탐색 트리)로 구현한다. Red-Black Tree는 Binary Search Tree 중 self-balancing(자가 균형) 특성을 갖는다. 이 구조는 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드 기반 이진 탐색 트리이다. 이진 탐색 트리가 균형이 잡히면 모든 작업을 O(log n) 안에 실행 가능하다.
- 모든 노드에서 왼쪽과 오른쪽 자식의 높이 차는 최대 +/- 1
- 새로운 element가 들어왔을 때 트리 조정을 통해서 적절하게 위치를 설정
🦥 set의 생성자와 초기화
set 헤더 추가
#include <set>
1) 비어있는 set s 생성
set<int> s;
2) 내림차순 정렬 set 생성
default는 오름차순(less), greater<int>는 내림차순 정렬
// 아래 식에서 greater<int> 자리에 선언한 함수를 기준으로 정렬
set<int, greater<int>> s;
3) 복사본을 원소로 하는 컨테이너 생성
set<int> s(s2);
set <int> s2(s1.begin(), s1.end());
🦥 set의 함수들
🌴 Iterator
Iterator를 활용하여 set의 원소에 접근할 수 있다
s.begin(): set의 첫번째 원소를 가리키는 iterator 리턴s.end(): set의 마지막 원소 다음을 가리키는 iterator 리턴 (마지막 원소 아님!!)
/* set의 모든 원소 출력 */
for (auto i = s.begin(); i != s.end(); i++) {
cout << *i << endl;
}
🌴 Fuction
set 컨테이너의 멤버 함수들
1) set 크기 관련
s.size(): set의 element 개수 리턴s.empty(): set이 비어있는지 여부 리턴
2) 원소 탐색 관련
s.lower_bound(k): k의 iterator를 리턴s.upper_bound(k): 정렬된 순서를 기준으로 k 다음 원소의 iterator를 리턴s.find(k): k를 가리키는 iterator 리턴, k가 없으면 end()와 같은 iterator 리턴
3) 원소 삭제
s.erase(it): iterator가 가리키는 원소 삭제s.erase(it1, it2): [it1, it2) range의 원소 삭제s.clear(): set의 모든 원소 삭제
4) 원소 삽입
s.insert(k): 원소 k를 정렬된 위치에 삽입. 리턴 값으로 pair(원소와 성공 여부) 출력
▶ set의 insert 함수 추가 설명
- insert 함수의 return 값 자료형은 <iterator, bool> pair
ret.first는 삽입한 위치에 대한 iterator 리턴, ret second는 성공 여부를 리턴한다.
/* insert 함수 정의*/ pair<iterator,bool> insert (const pair<const Key, Type>& val); /* 실습 코드 */ pair<set<int>::iterator, bool> ret = s2.insert(10); if (ret.second) cout << "success" << endl; else cout << "fail" << endl; - iterator가 가리키는 위치부터 탐색하여 k를 삽입. 잘 활용하면 원소를 효율적으로 삽입할 수 있다.
set<int> s; it = s.find(30); s.insert(it, 40);
실습 코드
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int main(void) {
set <int, greater<int>> s;
set <int> s2;
int list[] = { 10, 30, 50, 80, 40, 20 };
s2.insert(list, list+6);
s.insert(2);
s.insert(1);
s.insert(5);
s.insert(9);
s.insert(3);
s.insert(4);
auto ret = s.insert(8);
s.insert(5);
cout << "ret.first(return element) : " << *ret.first << endl;
cout << "ret.second(return true/false) : " << ret.second << endl;
cout << "show all elements in s" << endl;
for (auto i = s.begin(); i != s.end(); i++) {
cout << *i << " ";
}
cout << endl;
cout << "show all elements in s2" << endl;
for (auto i = s2.begin(); i != s2.end(); i++) {
cout << *i << " ";
}
cout << endl;
cout << "\nrun s.erase(9)" << endl;
int ret2 = s.erase(9);
cout << ret2 << "개의 원소 erased!" << endl;
for (auto i = s.begin(); i != s.end(); i++) {
cout << *i << " ";
}
cout << endl << endl;
cout << "lower_bound(5) : " << *s.lower_bound(5) << endl;
cout << "upper_bound(5) : " << *s.upper_bound(5) << endl;
for (auto i = s.lower_bound(8); i != s.upper_bound(3); i++) {
cout << *i << " ";
}
cout << endl << endl;
cout << "run s.find()" << endl;
for (auto i = s.find(8); i != s.find(3); i++) {
cout << *i << " ";
}
cout << endl << endl;
cout << "run s.clear() if s is not empty" << endl;
if (!s.empty()) {
s.clear();
}
for (auto i = s.find(8); i != s.find(3); i++) {
cout << *i << " ";
}
cout << endl;
}
[실행 결과]
ret.first(return element) : 8
ret.second(return true/false) : 1
show all elements in s
9 8 5 4 3 2 1
show all elements in s2
10 20 30 40 50 80
run s.erase(9)
1개의 원소 erased!
8 5 4 3 2 1
lower_bound(5) : 5
upper_bound(5) : 4
8 5 4 3
run s.find()
8 5 4
run s.clear() if s is not empty
🦥 multiset?
multiset은 set과 거의 동일하지만, 중복된 key값을 허용하는 컨테이너이다.
🦥 multiset의 생성자와 초기화
set 헤더 추가
#include <set>
1) 비어있는 multiset 생성
multiset<int> mts;
2) 내림차순 정렬 set 생성
default는 오름차순(less), greater<int>는 내림차순 정렬
// 아래 식에서 greater<int> 자리에 선언한 함수를 기준으로 정렬
multiset<int, greater<int>> mts;
3) 복사본을 원소로 하는 set 생성
multiset<int> mts(mts2);
multiset<int> mts2(mts1.begin(), mts1.end());
🦥 multiset의 함수들
🌴 Iterator
set과 동일
🌴 Fuction
set과 거의 동일하기 때문에 다른 부분만 아래에 설명
s.lower_bound(k): 원소 k가 있는 구간의 처음을 가리키는 iterator 리턴s.upper_bound(k): 원소 k가 있는 구간의 끝(그 다음 원소)을 가리키는 iterator 리턴s.equal_range(k): 원소 k가 있는 구간을 나타내는 pair 객체 리턴. pair의 원소는 (lower_bound, upper_bound)
실습 코드
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int main(void) {
multiset <int, greater<int>> mts;
mts.insert(2);
mts.insert(1);
mts.insert(5);
mts.insert(9);
mts.insert(9);
mts.insert(9);
mts.insert(3);
mts.insert(4);
auto ret = mts.insert(8);
mts.insert(5);
mts.insert(5);
cout << "insert ret : " << *ret << endl << endl;
cout << "show all elements in mts" << endl;
for (auto i = mts.begin(); i != mts.end(); i++) {
cout << *i << " ";
}
cout << endl << endl;
cout << "run mts.erase(9)" << endl;
int ret2 = mts.erase(9);
cout << ret2 << "개의 원소 erased!" << endl;
for (auto i = mts.begin(); i != mts.end(); i++) {
cout << *i << " ";
}
cout << endl << endl;
cout << "lower_bound(5) : " << *mts.lower_bound(5) << endl;
cout << "upper_bound(5) : " << *mts.upper_bound(5) << endl;
for (auto i = mts.lower_bound(5); i != mts.upper_bound(5); i++) {
cout << *i << " ";
}
cout << endl << endl;
cout << "run equal_pair" << endl;
auto p = mts.equal_range(5);
for (auto i = p.first; i != p.second; i++) {
cout << *i << " ";
}
}
[실행 결과]
insert ret : 8
show all elements in mts
9 9 9 8 5 5 5 4 3 2 1
run mts.erase(9)
3개의 원소 erased!
8 5 5 5 4 3 2 1
lower_bound(5) : 5
upper_bound(5) : 4
5 5 5
run equal_pair
5 5 5
Reference
Leave a comment