김상구.패패루 님이 쓰신 글 :
: 만해야.. 내다.. 패패루
:
: 소스는 보지두 않아따.. 켜켜켜
:
: 근데 대충 봐떠니만 map을 쓸 때 키값을 쓰면서도 또 스트럭쳐에 집어넣더구나..
: 용량 두배다..
: URL 값은 엄청 긴 경우 많다..
: 80byte가 아니라 800byte는 되어보인다..
: 게다가 map은 AVL Binary Search Tree다..

map은 여러가지의 Balanced Binary Search Tree 중 Red-Black Tree를 사용합니다.
소스코드를 뒤져 보면 _Rb_tree 로 시작하는 타입이 많이 나오죠.
AVL 트리보다 약간 더 빠르다고 하네요.

: 노드 하나 증가할 때 최소 몇바이트가 필요하겄냐..
: Parent, Left, Right..  데이터 없이도 기본 12바이트다..
: 그것만 있겄냐.. STL에서 사용할 데이터들.. 기타등등 합치면 노드 하나 추가되는거
: 만만치 않다.. 근데 키값까지도 중복해서 저장하면.. 키를 그냥 int같은거 쓰는 것도
: 아니고 스트링을 키로 쓰는디.. 어찌 그게 용량을 적게 묵겠능가
:
: 바이너리 서치트리가 제아무리 검색속도가 빠르다구 해도 지난번에 네가 올린 소스처
: 럼 쓰면 검색량 엄청나다.. 1000개면 균형이 맞아도 10레벨이고.. 스트링 비교 최소한
: 10번은 들어가는데.. 그렇게 [] 연산자로 뒤지믄 어케하란마리냐..

속도면에서는 상수 시간이 걸리는 hash_map을 써보는 것도 좋지요.
하지만 용량은 더 많이 들지요.

: vector의 경우 카파시티가 이따..
: 늘어나는건 맘대로 느러나지만 줄어드는건 맘대로 안된다.

줄어드는 것도 가능하다는 것은 만해님이 인용한 대로구요.

: 최종 사이즈는 10이라도 실제 캐퍼시티는 100이 될 수도 있고 10000이 될 수도 이따..
: 이런거 다 고려했느냐..
:
: 이런 뎐차로.. 만약 노드 하나가 800byte에 1000개면 거진 1메가다..
: 이런거 10개 있음 대충 10메가다..
: 게다가 카파시티 고려 안했다믄.. 또 엄청 는다..
:
: HeapAlloc 썼다면 또 역시.. 줄어들지 않는 메모리 이따.. 메모리 릭은 아니다..
:
: 소스는 안봐쓰니 머라 할 마른 엄다믄서도..
: 가뜨기나 내 쏘쓰 보기두 머리아픈데 메모리 누수 잡느라 새 쏘쓰 보기 구찬타..
: ㅋㅋㅋ
:
: 아무튼. 잘해보라는 얘기쥐~~~~
:
: