VC7에 포함된 STL set의 데이터 할당 구조

std::set<int> setData;

int nSize = sizeof(setData);
int nNodeSize = sizeof(*listData._Myhead);



nSize의값은 12라고 나타난다.
nNodeSize의값은 20이라고 나타난다.

watch창을 살펴보쟈..



setData
  +-- allocator..
  +-- _Myhead
  |      +-- _Left      // left subtree, or smallest element if head
  |      +-- _Parent    // parent, or root of tree if head
  |      +-- _Right     // right subtree, or largest element if head
  |      +-- _Myval     // the stored value, unused if head
  |      +-- _Color     // _Red or _Black, _Black if head
  |      +-- _Isnil     // true only if head (also nil) node
  +-- _Mysize



알다시피 set컨테이너는 balance 2진트리 구조를 가지고 있다.
데이터 노드는 Left,Right 그리고 Parent를 가지고 있게 될 것이다.


xtree라는 파일을 열어 set컨테이너의 초기화 함수를 살펴보자..


void _Init()
{ // create head/nil node and make tree empty
 _Myhead = _Buynode();
 _Isnil(_Myhead) = true;
 _Root() = _Myhead;
 _Lmost() = _Myhead, _Rmost() = _Myhead;
 _Mysize = 0;
}


set 역시 최초에 head-node를 생성시킨다.(생성시 _Color값은 _Black로 _Isnil은 false로 설정된다)

이 노드는 데이터가 없으므로 _Isnil을 true로 설정.
이 노드가 루트노드로 설정한다.(위 코드를 풀어쓰면.. _Myhead->_Parent = _Myhead;  와 같다.)
좌측 서브 노드와 우측 서브노드 역시 자신으로 설정한다.
Size를 0으로 셋팅.


이 node의 left,right,parent모두 head-node의 주소를 가르키고 있다.


데이터를 여러개 넣은 뒤 데이터의 구조를 살펴보면 간단한 특징을 확인할 수 있다.


head-node의 parent는 트리의 루트를 가르킨다.
head-node의 left-node는 최좌측 노드를 가르킨다.(가장 적은 숫자)
head-node의 right-node는 최우측 노드를 가르킨다.(가장 큰 숫자)



* _Color 값은 tree를 구축할때 사용되어지는것 같다...