C++ set 사용법과 설명...
set에 대해 설명하고자 합니다. 사용법도요.
아마 set을 사용하려고 검색하셔서 오시게 된 분이시라면,
set의 특징을 잘 아시는 분일겁니다.
네, set의 특징은 다음과 같습니다.
1. 숫자든 문자든 중복을 없엔다.
2. 삽입하는 순서에 상관없이 정렬되서 입력이 된다.
이 특징을 모두 만족시킬 수 있는 자료구조는 이진 트리 입니다.
즉, set은 벨런스 트리로 Red-Black 트리로 만들어져 있습니다.
이런식으로 말이죠...
이진트리 특성상 삽입과 삭제가 용이합니다. 자료 찾는것도 준수하고요.
그럼 사용법을 알아보겠습니다.
Set의 초기화
| set<자료형> 변수 | 기본적인 선언방법 |
| set<자료형> 변수(복사할 변수) | 선언 후 복사한 값으로 초기화 |
| set<자료형> 변수 = 복사할 변수 | 서언 후 복사한 값으로 초기화 |
#include <iostream>
#include <set>
using namespace std;
int main(void) {
set<int> s;
s.insert(1);
s.insert(200);
s.insert(-1);
s.insert(3);
int arr[] = { 1, 2, 3, 4, 5, 6 };
set<int> s1(s.begin(), s.end()); //output : s1 = -1, 1, 3, 200
set<int> s2(arr, arr + 6); //output : s2 = 1, 2, 3, 4, 5, 6
set<int> s3(s1); //output : s3 = -1, 1, 3, 200
set<int> s4 = s2; //output : s4 = 1, 2, 3, 4, 5, 6
return 0;
}
Set의 반복자(iterator)
| s.begin() | set의 시작이 되는 주소 값 반환 |
| s.end() | set의 마지막 부분에 대한 주소 값 반환(정확히는 마지막 뒤 공백구간) |
| s.rbegin() | set의 마지막 부분을 시작점으로 지정 |
| s.rend() | set의 첫번 째 부분을 마지막점으로 지정 |
| s.cbegin() | begin()과 동일하지만 const로 설정. |
| s.cend() | end()와 동일하지만 const로 설정 |
| s.crbegin() | rbegin()과 동일하지만 const로 설정 |
| s.crend() | rend()와 동일하지만 const로 설정 |
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main(void) {
set<int> s;
s.insert(1);
s.insert(200);
s.insert(-1);
s.insert(3);
for_each(s.begin(), s.end(), [](int n) {
cout << n << endl; //output : -1, 1, 3, 200
});
for_each(s.rbegin(), s.rend(), [](int n) {
cout << n << endl; //output : 200, 3, 1, -1
});
return 0;
}
출처 : https://en.cppreference.com/w/cpp/container/vector/rend
Set의 용량(Capacity)
| s.empty() | s가 비어있다면 true, 아니면 false |
| s.size() | s에 저장되어 있는 크기 |
| s.max_size() | s가 가질 수 있는 최대 크기 |
#include <iostream>
#include <set>
using namespace std;
int main(void) {
set<int> s;
s.insert(1);
s.insert(200);
s.insert(-1);
s.insert(3);
cout << s.empty() << endl; //output : 0(false)
cout << s.size() << endl; //output : 4
cout << s.max_size() << endl; //output : 214748364
return 0;
}
Set의 삽입, 삭제(Modifiers)
| s.insert() | s에 값 삽입 |
| s.erase() | s에 저장된 요소 삭제 |
| s.swap() | s1과 s2를 서로 교환 |
| s.clear() | s의 요소들 전부 삭제 |
| s.emplace() | move()를 사용해 객체를 저장 |
| s.emplace_hint() | 삽입될 위치에 대한 힌트를 토대로 삽입 |
#include <set>
using namespace std;
int main(void){
set<int> s;
s.insert(5);
s.insert(2);
s.insert(10);
s.insert(1);
//output : 1, 2, 5, 10
//////////////////////
set<int> s1;
s1.emplace(100);
s1.emplace(50);
s1.emplace(1);
s1.emplace(4);
set<int>::iterator itr = s1.emplace_hint(s1.end(), 101); //삽입속도 빠름
s1.emplace_hint(itr, 1); //삽입 속도 느림
//output : 1, 4, 50, 100
////////////////////////
set<int> s2;
s2.insert(10);
s2.insert(5);
pair<set<int>::iterator, bool> check = s2.insert(10);
if (check.second)
cout << "삽입 완료" << endl;
else
cout << "삽입 실패(중복 값)" << endl;
//output : 삽입 완료
auto check_2 = s2.emplace(12);
if (check_2.second)
cout << "삽입 완료" << endl;
else
cout << "삽입 실패(중복 값)" << endl;
//output : 삽입 실패(중복 값)
///////////////////////////////////////////////////
set<pair<int, int>> s3;
s3.insert(make_pair(1, 2)); //ok!!
s3.insert(3, 4); //error!!
s3.emplace(3, 4); //ok!!
s3.emplace(1, 2); //ok!! put overlap!!
for(auto itr = s3.begin(); itr != s3.end(); itr++)
cout << (*itr).first << " " << (*itr).second << endl;
//output : (1 2) (3 4)
////////////////////////////////
s1.swap(s2); //s1 and s2 swap
s3.clear(); //s3 element remove....
////////////////////////////////
set<int> s4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
s4.erase(s4.find(1)); //output : 2, 3, 4, 5, 6, 7, 8, 9, 10
s4.erase(s4.begin(), s4.find(7)); //output : 7, 8, 9, 10
return 0;
}
insert와 emplace는 기본적인 반환 값이 pair<iterator, bool> 입니다.
즉, pair로 반환이 됩니다.
여기서 pair.first에는 삽입한 위치에 대한 iterator를 반환하고
pair.second에는 삽입 성공여부에 대한 bool 값이 들어가게 됩니다.
insert와 emplace의 차이는 53행과 55행을 보면 알 수 있는데,
insert는 rvalue에 대한 삽입은 안되지만 emplace는 가능한걸 볼 수 있습니다.
이는 emplace의 move연선자로 인한 불필요한 복사생성자의 호출을 제한하기 때문인데,
insert는 main에서 복사생성자 호출로 값이 삽입되지만
emplace는 set객체 내부에서 그 값이 생성되어 복사생성자 호출이 줄어들게됩니다.
(insert는 복사생성자를 2번 호출, emplace는 1번만 호출)
이는 c++의 containers library에 있는 모든 자료구조 객체에 있는 기능입니다.
emplace_hint()에 대한 기능은 21행과 22행에 있는데,
솔직히 속도에 차이는 얼마나지 않습니다.
하지만 분명한것은 emplace_hint()에 들어가는 위치에 따라 삽입의 속도는 차이가 있음이 분명합니다.
(https://en.cppreference.com/w/cpp/container/set/emplace_hint 를 참조하시길 바랍니다.)
Set의 기능(operations)
| s.find() | 찾는 값이 있으면 해당 위치의 iterator 반환, 아니면 s.end()반환 |
| s.count() | set에 저장된 요소들의 갯수 반환 |
| s.lower_bound() | set의 요소의 위치에 대한 iterator 반환 |
| s.upper_bound() | set의 요소의 위치에 대한 iterator 반환 |
| s.equal_range() | 해당 요소에 대한 범위(iterator) 반환 |
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
set<int> s = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
pair<set<int>::iterator, set<int>::iterator> itr = s.equal_range(4);
cout <<*itr.first << " " << *itr.second << endl; //output : 4, 5
set<int>::iterator low_itr, up_itr;
low_itr = s.lower_bound(3);
up_itr = s.upper_bound(7);
s.erase(low_itr, up_itr);
for_each(s.begin(), s.end(), [](int n) {
cout << n << endl; //output : 1, 2, 8, 9, 10
});
return 0;
}
lower_bound()와 upper_bound()는 set에 있는 요소를 삭제할 때 좋습니다.
s.erase(s.begin(), s.find(7)); 로 할 경우 1, 2, 7, 8, 9, 10 이 되므로 7은 유지되지만
s.erase(low_itr, up_itr);로 할 경우 1, 2, 8, 9, 10이 됩니다.
때문에 가독성이나 결과값 예측에도 lower, upper가 좋습니다.