Set Container Iterating

Map Container에 이어서 Set Container Iterating에 대해서 측정해 보았다.

Map Container와 마찬가지로 Functor Iterating을 이용하여 측정하였다.

측정 환경 : Visual Studio 2008
측정 컨테이너 :
    1. std::set
    2. stdext::hash_set
    3. boost::unordered_set
측정 방법 : Functor


boost::unordered_set의 경우 컨테이너의 element가 1천개가 되더라도 bucket이 1:1.5로 생기는 것을 확인하였다.
(약 1.5배의 Bucket이 생성되었다.)

Hash 알고리즘에서 Collision이 발생하지 않도록 Bucket을 생성하는 것이 핵심인데,
VisualStudio 2008의 std::hash_set에서는 Type을 고려하지 않고 동일한 해쉬 함수를 사용하는데,
boost::unordered_set은
    1. std::numeric_limits로 해당 타입의 크기
    2. signed / unsigned
를 고려하여 해쉬 Seed 값을 생성하여 사용하기 때문에 각각의 Type 특성에 맞는 해쉬 키를 사용한다.


2010/04/11 23:41 2010/04/11 23:41

글 걸기 주소 : 이 글에는 트랙백을 보낼 수 없습니다

덧글을 달아 주세요