[TR1 살펴보기] 3. UnOrdered Containers

by Lyn posted Oct 05, 2008
?

단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄
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 이란 용어를 사용했다.