|
STL 에서는 B-Tree 기반의 Collection 이 준비되어 있는데, set ,multiset ,map ,multimap 의 4 종류이다.
그에 반헤 TR1에서는 위의 4종류의 Collection 에 대응되는 Hash 기반의 Collection 을 제공한다.
이름하여 unordered 시리즈(unordered_set, unordered_multiset, unordered_map, unordered_multimap) 이다. (이름너무 길다)
기본적인 사용법은 STL 의 콜렉션과 완전히 같으니 그냥 무시하도록 하겠다.
제일 기본적인 unordered_set 에 대해서만 예제를 보자
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
using namespace std::tr1;
int main()
{
unordered_set<string> UnOrderSet;
UnOrderSet.rehash(10); //버켓의 갯수를 정의한다.
//UnOrderSet.insert("김호광");
UnOrderSet.insert("남병철");
UnOrderSet.insert("류종택");
UnOrderSet.insert("린");
UnOrderSet.insert("박지훈");
if(UnOrderSet.find("김호광") != UnOrderSet.end())
{
cout << "김호광 님은 볼랜드 포럼 회원입니다." << endl;
}
else
{
cout << "김호광 님은 볼랜드 포럼 회원이 아닙니다." << endl;
}
}
위에말한대로 기본적인 사용법은 set 과 완전히 동일하다.
중요한 것은 rehash 매소드. 버켓의 갯수가 너무 많으면 메모리 낭비가 극심해지고, 너무 작으면 성능이 나빠집니다. 이래저래 귀찮은 Collection 이라 할 수 있겠군요
기본적으로 unordered_set 은 4개의 템플릿 인수를 받아드립니다.
Value(사용할 Type), Hash(Value 를 Hash화 하는 함수객체), Pred(비교함수객체), Alloc(할당자)의 순서인데
Hash, Pred, Alloc 은 디폴트 파라미터가 있으므로 사용 하지 않아도 무방하다.
만약 기본적으로 C++에서 제공하는 놈(int, string, double 등등...) 들이 아닌 다른놈들을 사용하려면?
2가지 구현이 필요하다.
첫째로 == 연산자의 오버로딩, 두번째로 해시함수객체의 제공이다. unordered_set의 2번째 파라메터인 Hash를 내가 사용하기 원하는 타잎을 Hash 할 수 있도록 제공 해 주는것이 필수적이다.
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
using namespace std::tr1;
struct TTest
{
int i;
double d;
bool operator == (const TTest &T) const
{
return ((i == T.i) && (d == T.d));
}
};
struct TTestHash
{
size_t operator () (const TTest &T) const
{
return T.i; //그냥 간단하게 i값을 해시값 취급 해버렷다
}
};
int main()
{
TTest test[2];
unordered_set<TTest, TTestHash> UnOrderSet;
test[0].i = 5;
test[0].d = 3.14;
test[1].i = 9;
test[1].d = 180.36;
UnOrderSet.insert(test[0]);
UnOrderSet.insert(test[1]);
TTest FindValue;
FindValue.i = 5;
FindValue.d = 3.15;
if(UnOrderSet.find(FindValue) != UnOrderSet.end())
{
cout << "찾는 객체가 있습니다" << endl;
}
else
{
cout << "찾는 객체가 없습니다" << endl;
}
}
위처럼 사용자 정의타잎 TTest 를 정의하고, 그에대한 해시함수객체 TTestHash 를 정의한 후, unordered_set 을 생성할 시에, Hash함수 객체 타잎을 제공하엿다.
결론을 내자면...
1. 기본타잎을 쓰더라도 어느정도 데이터의 양을 예측 해야 만족스러운 성능이 나온다.
2. 사용자 정의타잎을 쓰고 싶으면 Hash 를 재정의 해야 하기때문에 얼마나 Hash 를 잘 시키느냐에 따라 성능이 크게 달라진다.
3. 위의 조건을 다 만족시킨다면 상황에따라 다르겠지만 대충 set 의 2배정도의 성능을 보여주는 것 같다(속도측면, 메모리는 아무래도 소비가 크다)
4. C++ Collection 너무 많다 =_=;;; 상황에 따라 최적의 Collection 을 찾는 것 만도 일이다.
5. STL 의 Collection 들은 별 존재가치가 없어졋단 생각도 든다... 메모리 아껴야되는 상황이 아니라면(오해의 소지 매우 많음!)
Ps. C++ 에서는 보통 Containers 라 하는 것 같은데... 익숙하지 않아 그냥 일반적인 Collection 이란 용어를 사용했다.
|
그럼