STL에 있는 자료구조중 하나인 map 은 내부가 뭘로 구현 되어 있나요?
tree 로 구현되 있을 법 한데. 만약 그렇다면, 어떤 tree 로 구현이 되는건가요? 표준안에 그런제약 사항이 특별히 없다면, SGI 의 STL 에 있는 map 은 어떤 알고리즘을 이용해서 구현이 된건가요?
hash 역시(비표준이지만) 알고리즘이 다양하던데, SGI STL의 hash 는 어떤 알고리즘으로 구현이 됐는지 궁금하네요.
표준은 map의 구현에 대해서는 정하지 않았지만 흔히 red-black tree로 구현한다고
하더군요. (저는 전산쪽 백그라운드가 없어서 그게 구체적으로 뭔지는 모릅니다. ^^; )
SGI 계열에 속하는 STLport나 gcc가 그렇고 VC++의 Dinkumware도 그렇습니다.
hash 컨테이너는 SGI와 Dinkumware 두 계열의 인터페이스나 구현이 상당히 다르고요.
현재 진행중인 표준 개정 초안의 unordered_*가 hash 기반 컨테이너인데,
인터페이스를 보면 SGI와 비슷해 보입니다. 기존의 hash_* 클래스와 혼동을
피하기 위해서 이름을 그렇게 지었다고는 하지만 별로 마음에 들지는 않는군요.
표준은 map의 구현에 대해서는 정하지 않았지만 흔히 red-black
표준은 map의 구현에 대해서는 정하지 않았지만 흔히 red-black tree로 구현한다고
하더군요. (저는 전산쪽 백그라운드가 없어서 그게 구체적으로 뭔지는 모릅니다. ^^; )
SGI 계열에 속하는 STLport나 gcc가 그렇고 VC++의 Dinkumware도 그렇습니다.
hash 컨테이너는 SGI와 Dinkumware 두 계열의 인터페이스나 구현이 상당히 다르고요.
현재 진행중인 표준 개정 초안의 unordered_*가 hash 기반 컨테이너인데,
인터페이스를 보면 SGI와 비슷해 보입니다. 기존의 hash_* 클래스와 혼동을
피하기 위해서 이름을 그렇게 지었다고는 하지만 별로 마음에 들지는 않는군요.
댓글 달기