[ 연관 컨테이너 ]
연관 컨테이너는 특정 정렬 기준(조건자)에 따라 원소를 자동 정렬 하는 컨테이너 입니다. 이때 정렬 기준은 템플릿 매갭변수에 지정 할 수 있으며, 기본 정렬 기준은 less 조건자입니다. 그렇다 보니 시퀀스 컨테이너에서 순서와 관련된 함수류인 push_back(), push_front(), pop_back(), pop_front(), front(), back()을 제공하지 않습니다.
또한, 연관 컨테이너의 핵심은 빠른 원소 찾기이며, 균형 이진 트리를 사용하므로 찾기 연산(find(), lower_bound(), upper_bound(), equal_range(), count())에 뛰어난 성능(로그시간)을 보이며 insert() 멤버 함수를 이용한 삽입도 로그 시간 복잡도를 보입니다.
모든 연관 컨테이너의 key는 삽입, 검색, 제거등에 모두 이용됩니다. 그래서 모든 연고나 컨테이너의 key는 변경할 수 없습니다.
set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 key라 불리는 원소(value)의 집합으로 이뤄진 컨테이너 입니다.
모든 연관 컨테이너는 노드 기반 컨테이너 이며 균형 이진 트리로 구현 되므로 균형 이진 트리의 모든 특징을 가집니다.
[ set 컨테이너의 insert() 멤버 함수 ]
set은 컨테이너에 원소(key)를 저장(삽입)하는 유일한 멤버함수 insert()를 제공합니다.( 삽입관련 다른 함수 없음 )
set은 원소를 key라 하며 이 키를 비교하여 내부 원소를 정렬합니다.
set은 원소의 중복을 허용 하지 않습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <iostream> #include <set> using namespace std; int main(){ //정수 원소를 저장하는 기본정렬기준 less인 빈 컨테이너 생성 set<int> s; pair<set<int>::iterator, bool> pr; pr = s.insert(50); if( pr.second ){ cout<< *pr.first << " 삽입 성공!" <<endl; }else{ cout<< *pr.first << " 중복으로 삽입 실패!" <<endl; } s.insert(30); s.insert(80); s.insert(40); s.insert(10); s.insert(70); s.insert(90); pr = s.insert(30); //중복된 원소는 삽입 실패!! if( pr.second ){ cout<< *pr.first << " 삽입 성공!" <<endl; }else{ cout<< *pr.first << " 중복으로 삽입 실패!" <<endl; } set<int>::iterator Iter; for( Iter = s.begin(); Iter != s.end(); ++Iter ){ cout<<*Iter<<" "; // 10 30 40 50 70 80 90 } cout<<endl; system("pause"); return 0; } |
insert()멤버 함수는 원소의 중복을 허용하지 않기 때문에 반환값으로 실패를 확인할 수 있습니다.
반환값은 pair객체이며,
first와 second는 각각 삽입된 원소(key)의 위치를 가리키는 반복자와 true, false를 나타내는 boo l값입니다.
위의 예제에서 set의 구조
50
30 80
10 40 70 90
set의 반복자로 원소를 탐색하는 순서
- 10 30 40 50 70 80 90 ( 모든 노드의 부모노드는 왼쪽 자식노드보다 크고 오른쪽 자식노드보다 작습니다.)
위의 예제에서 쉽게 놓치는 부분중 하나는 pr.second가 성공이면 pr.first는 삽입한 원소(30)를 가리키는 반복이고, 실패하면 pr.first는 이미 삽입 되어있던 원소(30)를 가리키는 반복자 입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <iostream> #include <set> using namespace std; int main(){ // 정수 원소를 저장하는 기본정렬기준 less인 빈 컨테이너 생성 set<int> s; // 정렬 기준으로 greater<int> 조건자를 사용( > 오름차순 ) //set< int, greater<int> > s; /* 50 * 80 30 * * 90 70 40 10 */ pair<set<int>::iterator, bool> pr; s.insert(50); s.insert(30); s.insert(80); s.insert(40); s.insert(10); s.insert(70); pr = s.insert(90);// 삽입한 원소 pr.first(90) // 삽입할 위치지정 insert()멤버함수 사용 // pr.first가 가리키는 위치부터 탐색을 시작하여 85를 삽입합니다. s.insert(pr.first, 85);// 90의 원소의 반복자에서 검색 시작후 삽입 set<int>::iterator Iter; for( Iter = s.begin(); Iter != s.end(); ++Iter ){ cout<<*Iter<<" "; // 10 30 40 50 70 80 85 90 } cout<<endl; system("pause"); return 0; } |
위의 예제는 원소(key)의 삽입 위치를 지정하는 버전이며,
삽입 탐색을 시작할 위치로 삽입 위치가 정렬 순서와 맞는 다면, 바로 삽입되지만 아니라면 로그시간이 걸립니다. 즉! 삽입되는 원소가 탐색을 시작할 위치에 정렬순서상 맞는다면 바로 삽입 됩니다.
[ set의 key_comp(), value_comp() 멤버 함수 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <iostream> #include <set> using namespace std; int main(){ set<int, less<int>> s1; // 기준정렬 less 조건자 set<int, greater<int>> s2; // 기준정렬 greater 조건자 // s1 사용중인 정렬 기준 조건자를 리턴 set<int, less<int>>::key_compare l_cmp = s1.key_comp(); cout<< l_cmp(10, 20) << endl; // 10 < 20 연산 // s2 사용중인 정렬 기준 조건자를 리턴 set<int, greater<int>>::key_compare g_cmp = s2.key_comp(); cout<< g_cmp(10, 20) << endl; // 10 > 20 연산 cout<<endl; /** * set은 저장 원소인 값(value)이 곧 비교로 사용되는키(key)가됩니다. */ cout << "key_compare type : " << typeid(s1.key_comp()).name() << endl; cout << "value_compare type : " << typeid(s1.value_comp()).name() << endl; cout<<endl; cout << "key_compare type : " << typeid(s2.key_comp()).name() << endl; cout << "value_compare type : " << typeid(s2.value_comp()).name() << endl; system("pause"); return 0; } |
위의 얘제 key_comp(), value_comp()의 출력값이 같은 이유는
set 컨테이너는 저장 원소인 값(value)이 곧 비교로 사용되는 키(key)값 이기 때문 입니다.
[ set의 count() 멤버 함수 ]
| 1 | cout<< "원소 50의 갯수 : " << s.count(50) <<endl; |
set은 중복된 원소를 가지지 않아 컨테이너의 원소중 50인 원소는 1개 아니면 0개 이다. 굳이 count() 함수가 필요 있어 보이지는 않지만, 연관 컨테이너의 인터페이스는 모두 같으므로 set도 count() 멤버 함수를 제공 합니다. ( 실행시간 : 로그시간복잡도 )
[ set의 find() 멤버 함수 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream> #include <set> using namespace std; int main(){ set<int> s; s.insert(50); s.insert(30); s.insert(80); s.insert(40); s.insert(10); s.insert(70); s.insert(90); set<int>::iterator Iter; // 30원소의 반복자를 반환 // 30원소가 없으면, s.end()와 같은 반복자를 반환 합니다. // 연관컨테이너는 원소를 찾을 때 == 연산을 사용하지 않습니다. // 정렬 기준에 의해 key가 정렬되어 있으므로 // 컨테이너의 정렬 기준 조건자를 이용해 찾기 연산을 수행합니다. // !(*Iter<30) && !(30<*Iter) 30보다 작거나 크지 않다. // !s.key_comp()(a,b) && !s.key_comp()(b,a) 이면 두원소는 같음 Iter = s.find(30); // end() 멤버 함수가 끝 표시 반복자를 반환하므로 // end()멤버 함수와 비교해서 검색이 성공했는 유무를 판단 if( Iter != s.end() ){ cout<<*Iter<< "가 s에 있다"<<endl; }else{ cout<<"20이 s에 없다."<<endl; } // 30이 50보다 앞서 있지 않고 50도 30보다 앞서 있지 않은가? cout<< ( !s.key_comp()(30, 50) && !s.key_comp()(50, 30) ) <<endl; // false // 30이 30보다 앞서 있지 않고 30도 30보다 앞서 있지 않은가? cout<< ( !s.key_comp()(30, 30) && !s.key_comp()(30, 30) ) <<endl; // true system("pause"); return 0; } |
[ set의 lower_bound(), upper_bound(), equal_range() 멤버 함수 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include <iostream> #include <set> using namespace std; int main(){ set<int> s; s.insert( 50 ); s.insert( 30 ); s.insert( 80 ); s.insert( 40 ); s.insert( 10 ); s.insert( 70 ); s.insert( 90 ); set<int>::iterator Iter_lower; set<int>::iterator Iter_uppder; // 30이 시작하는 구간의 반복자 Iter_lower = s.lower_bound(30); // 30이 끝나는 구간의 반복자( 찾는 원소의 다음 원소 반복자) Iter_uppder = s.upper_bound(30); cout<< *Iter_lower <<endl; // 30 cout<< *Iter_uppder <<endl;// 40 if( Iter_lower != Iter_uppder ){ cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 있음!"<<endl; }else{ cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 없읍!"<<endl; } // 55 원소의 시작과 끝구간을 리턴 // 10 30 40 50 70 80 90 에서 55를 찾지못해 55의 다음 반복자 // 밑에 보면 리턴되는 원소의 반복자의 시작과 끝이 같으므로 해당원소없음 Iter_lower = s.lower_bound(55); //70 Iter_uppder = s.upper_bound(55);//70 if( Iter_lower != Iter_uppder ){ cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 있음!"<<endl; }else{ cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 없읍!"<<endl; } cout<<endl; // equal_range() 멤버 함수 사용 pair< set<int>::iterator, set<int>::iterator > pr; pr = s.equal_range(30); cout<< *pr.first << endl; cout<< *pr.second << endl; if( pr.first != pr.second ){ cout<<"s에 있음!"<<endl; }else{ cout<<"s에 없음!"<<endl; } system("pause"); return 0; } |
lower_bound(key) : 찾은 원소의 시작 반복자를 반환, 못찾았다면 입력된 key값의 다음 반복자 리턴
중복시 찾는 원소의 첫번째 원소( set은 해당사항없음 )
upper_bound(key) : 찾은 원소의 다음 원소를 가리키는 반복자를 반환, 못찾았다면 다음 반복자 리턴
[lower_bound, upper_bound) 구간에서 두 반복자가 같다면 찾는 원소가 없습니다.
equal_range(key) : lower_bound(), upper_bound()의 반복자 쌍을 pair객체로 반환 해줍니다.
'0x0001 > STL' 카테고리의 다른 글
| [C++ STL] 연관 컨테이너 - 맵(map) (0) | 2019.02.16 |
|---|---|
| [C++ STL] 연관 컨테이너 - 멀티셋(multiset) (0) | 2019.02.16 |
| [C++ STL] 시퀀스 컨테이너 - 리스트(list) (0) | 2019.02.16 |
| [C++ STL] 시퀀스 컨테이너 - 덱(deque) (0) | 2019.02.16 |
| [C++ STL] 시퀀스 컨테이너 - 벡터(vector) (0) | 2019.02.16 |