정체불명의 모모
Effective STL - Chapter3 [ STL 연관 컨테이너 ] 본문
이번 장에서 중점으로 봐야하는 내용을 보여드리겠습니다.
1. 상등 관계 와 동등 관계의 차이 파악
2. 비교 함수를 사용할 때 잊지 말아야 할 제약 사항
3. 포인터의 연관 컨테이너에 대해 커스텀 비교 함수를 쓸 때 좋은 점
4. key의 상수성질에 대한 실체
5. 연관 컨테이너의 효율을 향상 시키는 법
1. 상등 관계 와 동등 관계의 차이 파악
- 상등성 : operator ==
- 동등성 : operator <
- 동등성의 의미 : 정렬된 범위 안에 있는 객체 값들의 상대적인 순서의 위치로 판단
(서로의 값이 서로의 앞에 오지 않으면 그 두 값은 특정한 정렬 기준에 대해서 동등하다.) - 상등성의 의미 : 값이 같은지 틀린지 판단
▶ 연관 컨테이너에 사용되는 비교 함수 : less , greater
#include <iostream> #include <set> using namespace std; int main() { cout << "==================== less 비교함수 =======================" << endl; set<int , less<int>> sL; sL.insert(50); sL.insert(10); sL.insert(80); sL.insert(30); sL.insert(70); sL.insert(60); set<int , less<int>>::iterator iter; // 10 , 30 , 50 , 60, 70, 80 for(iter = sL.begin() ; iter != sL.end() ; iter++) cout << *iter << ' '; cout << endl; cout << "================== greater 비교함수 =====================" << endl; set<int , greater<int>> sG; sG.insert(50); sG.insert(10); sG.insert(80); sG.insert(30); sG.insert(70); sG.insert(60); set<int , greater<int>>::iterator iterG; // 80, 70, 60, 50, 30, 10 for(iterG = sG.begin() ; iterG != sG.end() ; iterG++) cout << *iterG << ' '; cout << endl; return 0; }
▶ 연관 컨테이너의 find 와 알고리즘 find의 차이점 (소,대문자 구분 하지 않는 set)
#include <iostream> #include <set> using namespace std; int ciStringCompare(const string & s1, const string & s2) { return strcasecmp(s1.c_str() , s2.c_str()); } struct CICStringCompare : public binary_function<string, string , bool> { bool operator()(const string& lhs, const string& rhs) const { return ciStringCompare(lhs, rhs); } }; int main() { set<string , CICStringCompare> ciss; ciss.insert("Dog"); ciss.insert("dog"); cout << "================ 연관 컨테이너의 find ================" << endl; if(ciss.find("dog") != ciss.end()) cout << "참" << endl; else cout << "거짓" << endl; cout << "================ 알고리즘의 find ================" << endl; if(find(ciss.begin() , ciss.end() , "dog") != ciss.end()) cout << " 찾았다 " << endl; else cout << " 못 찾았다 " << endl; return 0; }
위 의 코드 결과는 매우 흥미롭고 위 주제에 관한 결과가 나온다.
- 연관 컨테이너 find 결과 : "Dog" 와 "dog"는 동등 관계에(CIStringCompare 함수자에 의해) 있기 때문에 찾을 수 있습니다.
- 알고리즘 find 결과 : 상등관계로 찾기에 -> string("Dog") != string("dog") 찾지 못합니다.
위 내용 처럼 '연관 컨테이너'는 동등 관계 기반인 것을 알 수 있습니다.
표준 연관 컨테이너에 저장되는 데이터 요소는 정렬된 수서로 관리 되기 때문에, 모든 연관 컨테이너에는 요소를 정렬 하는데 사용되는 비교 함수(less, greater)가 반드시 필요합니다.
동등성은 비교 함수의 동작 원리에 따라 정해지며, 컨테이너를 인스턴스화 할 때 비교 함수를 딱 '하나' 지정해 주는 것 입니다.
비교 함수를 사용할 때 잊지 말아야 할 제약 사항 :
포인터를 저장하는 연관 컨테이너에 대해서 적합한 비교 타입을 정해주자
방법 : 비교 함수자의 템플릿을 만들어 주자!
- 일반
: 주소값이 정렬되어 있고, 데이터는 정렬이 되어 있지 않습니다.
... int main() { set<string*> ssp; ssp.insert(new string("Apple")); ssp.insert(new string("Watermelon")); ssp.insert(new string("Banana")); ssp.insert(new string("Mango")); ssp.insert(new string("Strawberry")); for(set<string*>::iterator it = ssp.begin() ; it != ssp.end() ; it++) cout << *it << endl; //0x10201a170 //0x10201a1c0 //0x10201a210 //0x10201a750 //0x10201a7a0 for(set<string*>::iterator it = ssp.begin() ; it != ssp.end() ; it++) cout << *(*it) << endl; // Apple , Banana , Mango , Strawberry , Watermelon }
비교 함수자 템플릿을 이용한 방법
: 템플릿을 이용해 주소값으로 정렬 하는 것이 아닌, 데이터의 값으로 정렬하게 만들어 주었습니다.
// Less
...
struct DereferenceLess
{
template<typename PtrType>
bool operator()(PtrType pT1 , PtrType pT2) const
{
return *pT1 < *pT2;
}
};
void print(const string *ps)
{
cout << *ps << endl;
}
int main()
{
set<string*, DereferenceLess> ssp;
ssp.insert(new string("Apple"));
ssp.insert(new string("Watermelon"));
ssp.insert(new string("Banana"));
ssp.insert(new string("Mango"));
ssp.insert(new string("Strawberry"));
for_each(ssp.begin(), ssp.end() , print);
// Apple , Banana, Mango , Strawberry , Watermelon
}포인터의 연관 컨테이너를 만드는 일과 컨테이너의 '비교 타입' 을 지정하는 일은 실과 바늘의 관계라고 생각하면 편합니다.
그렇기에 비교 함수자의 템플릿을 하나 만들어두면 아주 편리 합니다. (자동 정렬을 위해)
3. 포인터의 연관 컨테이너에 대해 커스텀 비교 함수를 쓸 때 좋은 점
: 연관 컨테이너용 비교 함수는 같은 값에 대해 false를 반환해야 한다.
" 연관 컨테이너의 "같다"라는 말은 "동등 하다"라는 뜻이다. "
- 일반적으로 같은 데이터를 넣었을 때(비교 함수 : less_equal)
template <typename T> void print(const T& t) { cout << t << "\t"; }; int main() { set<int , less_equal<int>> s; s.insert(10); <- 10A s.insert(10); <- 10B for_each(s.begin() , s.end() , print<int>); cout << endl; return 0; }
▶ '10A' 와 '10B'가 같은지 체크 하는 방법 (비교 함수 : less_equal)
| !(10A <= 10B) && !(10B <= 10A) | !(true) && !(true) | false && false |
: 결과는 false 이다. 즉, 10A 와 10B는 동등하지 "않다"
같은 값은 연관 컨테이너로써의 가치가 없어진다는 것이며, 컨테이너의 자료들을 신용할수 없다는 것을 의미한다.
즉, 연관 컨테이너의 연관 자체가 '무너 진다.' 라는 뜻이다.
그래서 연관 컨테이너의 요소를 정렬할때 쓰는 비교함수는 같은 값에 대해서 false를 리턴하도록 규정하였다.
- 무너 진다는 표현에 대해서
: 무너진다는 것은 신용할 수 없다라고 이해 하면 된다.
같은 값 2개를 컨테이너에 밀어 넣고(insert), 다시 빼와서(find) 확인하고자 할 때, 두개 중 무엇이 나올지 예측할 수가 없다.
※ 하지만 값은 key 값을 넣을 수 있는 multiset이 존재한다.
- 커스텀 비교 함수를 이용한 같은 값 체크 하는 방법(비교 함수 : Greater)
struct intPtrGreater1 { bool operator()(const int &ps1 , const int &ps2) const { // 같은 값이면 true를 반환 한다. return !(ps1 < ps2); } }; struct intPtrGreater2 { bool operator()(const int &ps1, const int &ps2) const { // 같은 값이면 false를 반환 한다. return ps2 < ps1; } }; int main() { set<int, intPtrGreater> sg; sg.insert(10); sg.insert(10); for_each(sg.begin(), sg.end(), print<int>); cout << endl; return 0; }
4. key의 상수성질에 대한 실체
: set과 multiset에 저장된 데이터 요소에 대해 키(Key)를 바꾸는 일은 피하자
모든 표준 연관 컨테이너는 내부에 저장되는 데이터 요소를 정렬해서 관리하며, 컨테이너의 정상적인 동작은 요소들이 정렬된 상태에서만 가능합니다.
- map과 multimap은 키값을 바꾸는 일이 불가능하다.
이유 : 객체에 저장되는 요소는 pair<const K, V> 이기 대문입니다.
여기서 키(key) 부분이 const K이기 때문에, 태생부터 바꿀 수가없습니다.
- set과 multiset은 key값을 바꾸는것이 가능하다.
이유 : set<t>, multiset<T> 타입의 객체를 보면, 저장되는 데이터 요소의 타입은 그냥 T 입니다.
그렇기에 값을 바꿀 수 있습니다.
아래의 코드는 요소가 정렬되는것에 관련이 없는 직원 데이터를 바꾼것 이기 때문에, set 객체를 훼손 시키지
않습니다.
- 왜 map 과 multimap에는 위와 같은 법칙이 적용 되지 않는 걸까?
: 표준화 위원회에서 map / multimap 의 키는 const이어야 하고, set / multiset의 값은 const 이면 안된다는 것 입니다.
set이나 multiset에 저장된 값을 변경하고자 한다면, 변경할 부분은 절대로 키 부분이 아니어야 한다는 것입니다.
만약 키 값을 건들면 컨테이너는 엉망이 되고, 이 컨테이너는 예기치 못한 동작을 수행하게 됩니다.
set / multiset / map / multimap 에 저장된 요소를 안전하게 바꾸는 방법
| 1 | 변경하고자 하는 컨테이너 요소의 위치를 찾습니다. |
| 2 | 변경하고자 하는 요소의 복사본을 만듭니다. (map 이나 multimap의 경우에는 사본의 첫째 요소를 const 타입으로 선언하지 않도록 주의하세요) |
| 3 | 컨테이너에서 그 요소를 없앱니다.(erase호출) |
| 4 | 만들어둔 복사본의 정보를 바꿉니다. |
| 5 | 복사본을 컨테이너에 새로 삽입 합니다. |
EmpIDSet se;
Employee selectedID;
...
// 1. 바꾸자 하는 요소를 찾습니다.
EmpIDSet::iterator i = se.find(selectedID);
if( i != se.end())
{
// 2. 요소를 복사합니다.
Employee e(*i);
// 3. 컨테이너에서는 그 요소를 지웁니다.
se.erase(i++);
// 4. 복사본을 수정합니다.
e.setTile("Corporate Deity");
// 5. 복사본을 원래 컨테이너에 삽입합니다.
se.insert(i,e);
}연관 컨테이너 대신에 정렬된 vector를 쓰는 것이 좋을 때가 있다.
- 표준 연관 컨테이너는 어떻게 생겼나?
: 전형적으로 균형 이진 탐색 트리로 구현되어 있습니다.
이 트리는 데이터 노드의 삽입, 삭제, 탐색이 임의대로 아무 때나 이루어지는 상황에 적합하도록 구현된 자료 구조입니다.
'삽입 / 삭제 / 탐색' 의 수행이 일정한 순서를 따르지 않으며, 다음에 어떤 동작이 이루어질 지 예측할 수 없습니다.
(즉, 데이터를 삽입했다가, 탐색을 하다가, 데이터를 삽입했다가, 데이터를 지웠다가. 다시 탐색을 하는 등의 동작을 하는데 안전된
성능을 보이도록 만들어졌다는 뜻입니다.) - 애플리케이션이 자료구조를 사용하는 단계 ( 이럴 경우 벡터를 이용 하는게 훨씬 이득입니다.)
1. 데이터 셋업(Setup) : 자료 구조를 하나 만듭니다.
이때 이루어지는 동작은 데이터 삽입 및 삭제가 대부분이며, 탐색은 일어나지 않습니다.
2. 데이터 탐색(Lookup) : 셋업이 끝난 자료 구조를 사용하여 원하는 정보가 들어 있는지 찾습니다.
대부분의 동작은 탐색입니다.
3. 데이터 재구성(Reorganize) : 자료 구조에 들어 있는 내용물을 바꿉니다.
대개 이때 기존의 데이터를 모두 지우고 새 데이터를 집어넣게 됩니다.
동작상으로 1단계와 흡사합니다. 이 단계가 끝나면 다시 2단계로 진입하니다.
위 와 같은 방식으로 자료 구조를 사용하는 애플리케이션이라면, 벡터가 연관 컨테이너보다 훨씬 나은 수행성능을 제공할 가능성이
높습니다.
왜냐하면 벡터의 요소가 정렬된 상태에 있을 때 binary_search, lower_bound, equal_range 등의 탐색 알고리즘을 제대로
적용할 수 있기 때문입니다.
(하지만, 모든 vector 가 아닌, 정렬된 vector의 경우 해당합니다.)
- 벡터가 연관 컨테이너 보다 훨씬 나은 수행성능을 하는 이유(정렬된 vector)
▶ 이유 1 : 메모리 크기 문제
: 연관 컨테이너 경우 객체 하나를 저장하는데 최소한 세개의 포인터를 담기 때문에 메모리가 오버헤드 됩니다.
▶ 이유2 : 메모리 참조 위치의 근접성
: 벡터는 연속 메모리 구조를 가지고 있기 때문에 요소의 접근이 빠르고 쉽지만, 그렇지 않은 노드 기반의 연관 컨테이너는
, 이동 경로가 가까운 노드 사이라 할 지라도 물리 메모리 위치가 가까울 거라는 보장을 할 수없습니다.
그렇기에 벡터가 요소 접근이 빨라 수행성능을 높입니다.
삽입 및 삭제 동작과 탐색 동작이 거의 섞이지 않을 경우에는 정렬된 벡터가 훨씬 낫다는 것입니다.
- 벡터를 map 이나 multimap을 대신하는 방법
: 벡터에 데이터를 페어로 넣으며, pair<Key , Value>로 선언해야 합니다.
- 벡터를 map/multimap을 대신할 때에는 정렬 함수 와 탐색 비교 함수를 만들어야 합니다.
: 탐색용 비교 함수는 키 타입의 객체와 페어 객체를 매개 변수로 받기에 첫째 매개 변수로 들어가는 데이터가
키 값인지, 페어 객체인지 알 수가 없다는 점입니다.
그래서 양쪽을 고려한 함수를 만들어야 합니다.
typedef pair<string, int> Data; class DataCompare { public: //정렬용 비교 함수 bool operator()(const Data& lhs, const Data & rhs) const { return keyLess(lhs.first , rhs.first); } //탐색용 비교 함수(형태1) bool operator()(const Data* lhs, const Data::first_type & k) const { return keyLess(lhs.first , k); } // 탐색용 비교 함수(형태2) bool operator()(const Data::first_type& k, const Data& rhs) const { return KeyLess(k, rhs.first); } private: // 실제로 비교 하는 함수 bool keyLess(const Data::fisrt_type && k1, const Data::first_type & k2)const { return k1 < k2; } };
5. 연관 컨테이너의 효율을 향상 시키는 법
: map::operator[], map::insert는 효율을 주의하여 선택하자
map<int, Widget> m;
m[1] = 1.50;- map의 operatpr[] 연산자 함수는 심각한 수행 성능의 저하가 일어 날 수 있습니다.
- 상황 : map에 k가 들어가 있지 않은 경우
1. 맵에 키 k가 들어 있는지 점검합니다.
2. 그렇지 않다면 k와 v가 페어로 묶여서 맵에 새로 '추가' 됩니다.
2-1). v의 기본 생성자를 이용하여 v 객체를 하나만듭니다.
2-2). 키 k 와 v를 함께 묶은 페어 개체를 만듭니다.
2-3). v 객체에 대한 참조자를 반환합니다.
2-4). 대입 연산자를 통해 v 객체의 값을 받습니다.
위 같은 상황에서는 operator[]로 데이터를 삽입하는 것 보다.
- insert를 이용하는 것이 비용 절감 효과가 더 큽니다.
이유 : opeartor[]연산자를 이용하면 위의 과정인 함수 호출들이 많이 일어 나게 됩니다.
그에 반에 insert 함수를 이용하면 한번의 함수 호출로 새로운 객체를 넣을 수 있습니다.
- 상황 : map에 키가 이미 들어 있는 경우
- operator[]가 효율 적입니다.
이유 : insert는 타입 매개변수를 넘겨야 합니다. 따라서 insert를 호출할 때 해당 타입의 객체를 생성했다가
소멸 시키는 과정이 필수로 들어갑니다. 즉 pair의 생성자와 소멸자가 호출 됩니다.
그뿐 아니라, Value 객체의 생성자와 소멸자도 같이 호출됩니다.
반면에 , operator[]는 pair 객체를 사용하지 않기 때문에 페어와 value 객체 모두에 대한 생성자와 소멸자가 호출 되지 않습니다.
map에 객체를 '추가' 또는 '갱신'에 효율적인 방법
- 추가 : 맵에 '추가'를 할 경우에는 operator[] 보다 insert가 효율적으로 낫습니다.
- 갱신 : 맵에 저장된 요소에 대한 '갱신'을 할 경우에는 insert보다 operator[]가 효율적으로 낫습니다.
현재는 표준이 아니지만, 해쉬 컨테이너에 대해 충분히 대비해 두자
: 저자는 해쉬 컨테이너 버전 두가지에 대해 설명을 해주었지만, 여기서는 'Hash map'에 대해 알아 보겠다.
- Hash_map의 자료구조?
: Hash_map의 자료구조는 "해쉬 테이블" 입니다.
해시 테이블에 자료를 저장할 때는 key 값을 해시 함수에 대입하여 버킷 번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장합니다.
그리고, 해쉬 컨테이너는 연관 컨테이너면서도 두 객체가 같은지를 알아볼 때 동등성이 아닌 상등성(equality) 검사를 합니다.
그렇기에 해쉬 컨테이너는 정렬을 하지 않습니다.(무의미) - Hash_map을 사용하는 경우
1. 많은 자료를 저장하고 ,검색 속도가 빨라야 한다.(정렬이 필요없는 상황)
2. 너무 비번하게 자료를 삽입, 삭제 하지 않는다.
https://blog.daum.net/coolprogramming/82
26. STL 컨테이너(set, multiset)
이번 장은 트리 자료구조를 이해하시면 조금 빠르게 공부할 수 있습니다. set과 multiset은 '연관 컨테이너'입니다. 모든 연관 컨테이너는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는
blog.daum.net
'프로그래밍(c++) > Effective STL(C++)' 카테고리의 다른 글
| Effective STL - Chapter5 [알고리즘(Algorithms) (0) | 2021.10.25 |
|---|---|
| Effective STL - Chapter4 [ 반복자(Iterators) ] (0) | 2021.10.01 |
| Effective STL - Chapter2 [ Vector 와 String ] (0) | 2021.08.20 |
| Effective STL - Chapter1 효과적인 컨테이너 02 (0) | 2021.08.04 |
| Effective STL - Chapter1 효과적인 컨테이너 01 (0) | 2021.08.04 |
'프로그래밍(c++)/Effective STL(C++)' Related Articles
more
Comments