VC7에 포함된 STL string의 할당 구조

간만에 Effective STL책을 다시 보면서..... 심심했던걸까나...쩝.

Visual Studio 2003으로 테스트 해본다..

VC6.0이나 다른 상위버전은 테스트 안해봐서 모르겠다..쩝 귀챠나서..



std:: string s1;
int nSize = sizeof(s1);



위와 같이 대충 끄적대고 나서.. 브레이크를 걸어보자..
nSize값은 28을 가지고 있다.



Watch창에서 s1을 살펴보면 다음과 같이 구성되어 있다.


  s1
   +--- std::_String_val<char,std::allocator<char>>
   |    (STL의 기본 Allocator)
   +--- _Bx
   |    (문자열 데이터의 정보)
   +--- _Mysize
   |    (문자열의 길이)
   +--- _Myres
        (컨테이너의 할당된 메모리 크기)

     
여기서 _Bx라는 넘을 살펴보면(xstring파일 참고) 아래과 같은 union으로 되어 있다.



union _Bxty
{ // storage for small buffer or pointer to larger one
     _Elem _Buf[_BUF_SIZE];
     _Elem *_Ptr;
} _Bx;



* _BUF_SIZE는 16으로 설정되어 있다.


대강 봐도 string의 데이터가 _BUF_SIZE보다 작으면 _Buf배열 안에..
크면 _Ptr의 포인터에 설정되게 구성되었으리라 판단된다..


테스트 해보니. 실제로 그렇다.. ^^;



string이 생성되면 문자열 데이터의 개수가 _BUF_SIZE 보다
작으므로(당연히) _Bxty._Buf[0]은 NULL값을 가지며 _Myres는 15라는 값을 가지게 된다.


그럼 15보다 큰 값을 넣어주면 어떻게 될까..
당연히 배열인 _Bxty._Buf는 무시되고 _Bxty._Ptr에 메모리가 할당되어 사용되어 진다.


그런데 _Myres값은 어떻게 변할까?.. 다시 말하면 할당되는 메모리의 최대 크기는
얼마씩 설정될까..?



20개의 문자열을 할당하고 테스트 해보면
_Myres의 값은 31의 값을 보여주게 된다. 즉 32byte가 할당되었다.
처음 16byte에서 단순이 2배로 설정한것일까?



이번엔 35개의 문자열을 할당하고 테스트 해보면
_Myres의 값이 47의 값을 보여주게 된다. @,@   63이 아니다.. ㄷㄷㄷ
배수로 늘어나는 것이 아님을 보여준다...



stirng의 _Copy함수를 열어보면 그속에 답이 있다.


메모리를 재할당하는 과정에서 아래와 같은 size를 계산하는
단순하고도 오묘한? 수식을 볼 수 있다.



size_type _Newres = _Newsize | _ALLOC_MASK;



위에서 _Newsize는 새로 배정한 문자열의 길이이며..즉 35라는 값이 들어온다.
_ALLOC_MASK값은 15로 설정되어 있다.


이 수식에 의해 47이라는 값이 _Newres에 설정되고 이 크기만큼 할당되게 되는것이다.
뭐 나름대로 깊은 뜻이 있으리라.. 생각하자.~



* resize로 다른 값을 설정해서 같은 현상이 나타난다. 쩝.



참고로 다른 라이브러리는 reference count처리를 한다고 하지만 VC7에 포함된 STL string은
그러한 기능은 없는것 같다. ref count가 보이지 않고.. 테스트 해봐도 마찬가지..

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를 구축할때 사용되어지는것 같다...

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

어디 까지나 VC7의 STL에만 해당되는 얘기지.. 다른 라이브러리는 검토한바 없으므로..

참고용으로만 알고 있자~.. ㅋㅋ



기본생성자에 의해 리스트 컨테이너가 만들어지면
최초 head-node가 1개 자동으로 만들어진다.



물론 노드안에는 짐작하는것과 같이 link 구조를 유지하기 위한
prev, next node를 가르키는 포인터 변수가 존재한다.
물론 데이터를 담기 위한 _Myval이라는 넘도 존재한다.


std::list<int> list1;



list를 하나 만들고 watch창으로 확인해보자..



list1
  |
  +-- allocator..
  |
  +-- _Myhead
  |      |
  |      +-- _Next
  |      |
  |      +-- _Prev
  |      |
  |      +-- _Myval
  |       
  +-- _Mysize



아무런 데이터가 없는 상태에서는 _Myhead의 주소와 _Next, _Prev의 주소가 같은것을 볼 수 있다.
물론 _Mysize는 0이다.



한개의 노드를 추가해보자.


list.push_back(100);


_Next, _Prev의 주소가 새로 추가된 노드의 주소로 변경된것을 확인할 수 있을것이다.
물론 _Mysize는 1로 바뀌었다



몇개의 노드를 더 추가해보고 살펴보면 링크 구조에서
Prev-node가 없거나 Next-node가 없을경우는 모두
처음에 생성한 head-node의 주소를 가르키는것을 확인할 수 있다.



어찌 보면 head-node가 연결되어 node들이 circle구조처럼 보일수도 있지만.
head-node의 기능은 end iterator의 기능일 뿐이니 오해하지 말자~.



다시 말해

list.begin()은 head-node의 next가 되는것이고
list.end()은 head-node 자신이 된다는 얘기이다..

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

VC7.0의 STL 기준으로..~ 다른 버전도 크게 다르지 않을꺼라 본다.~


deque는 내부적으로 고정된 크기의(16byte) 맵형식으로 처리한다.(포인터 배열)

*여기서 맵은 의미상 이름이고.. 그냥 하나의 할당된 메모리 블럭이라고 생각해도 무관하리라 본다.


데이터 타입 / 16 == 1개 맵에 담을수 있는 데이터 개수

deque에 push_front()와 push_back()명령이 이루어지면 내부적으로 2개의 맵이 생성되어진다.

push_back은 맵의 앞부분 부터 채워지고

push_front는 맵의 뒷부분 부터 채워진다.

채워지는 방향에 따라 다른 맵을 생성하므로 2개가 만들어진다...

당연한 얘기지만 내부에 적재되는 데이터가 많아지면 여러개의 맵이 생성되고 데이터가 누적되어 진다.
만약 데이터의 타입의 크기가 8보다 크다면 1개의 데이터 당 1개의 맵을 차지하게 된다.~

원도 프로그램에서 Consol Process Output캡춰하기

bool ExecuteNonConsolProcess(std::string sExeName, std::string sArguments) {

std::string sExecute = sExeName;

sExecute += " ";

sExecute += sArguments;

HANDLE hReadPipe, hWritePipe;

SECURITY_ATTRIBUTES securityAttr;

ZeroMemory( & securityAttr, sizeof(securityAttr));

securityAttr.nLength = sizeof(securityAttr);

securityAttr.bInheritHandle = TRUE;

CreatePipe( & hReadPipe, & hWritePipe, & securityAttr, 0);

STARTUPINFO sStartupInfo;

PROCESS_INFORMATION process_Info;

ZeroMemory( & sStartupInfo, sizeof(sStartupInfo));

ZeroMemory( & process_Info, sizeof(process_Info));

sStartupInfo.cb = sizeof(STARTUPINFO);

sStartupInfo.dwFlags = STARTF_USESTDHANDLES;

sStartupInfo.hStdInput = NULL;

sStartupInfo.hStdOutput = hWritePipe;

sStartupInfo.hStdError = hWritePipe;

BOOL bSuccessProcess = CreateProcess(0, (char * ) sExecute.c_str(), 0, 0, TRUE, NORMAL_PRIORITY_CLASS | CREATE_NO_WINDOW,

0, 0, & sStartupInfo, & process_Info);

CloseHandle(hWritePipe);

if (FALSE == bSuccessProcess) {

CloseHandle(hReadPipe);

return false;

}

char szTemp[260];

DWORD dwReadByte;

std::string sOutputString;

sOutputString.clear();

BOOL bResult;

do {

ZeroMemory(szTemp, sizeof(szTemp));

bResult = ::ReadFile(hReadPipe, szTemp, sizeof(szTemp) - 1, & dwReadByte, 0);

if (TRUE == bResult) {

TRACE("%s", szTemp);

sOutputString += szTemp;

}

} while (TRUE == bResult);

CloseHandle(hReadPipe);

return true;

}

유용한 STL알고리즘

fill
주어진 초기값으로 벡터를 채운다.

copy
수열을 복사한다. 

generate
발생기(generator)가 생성한 값을 벡터에 집어넣는다.

find
조건을 만족하는 원소를 찾는다. 

adjacent_find
연속적으로 중복된 원소를 찾는다. 

search
벡터내에서 서브 시퀀스를 찾는다.

max_element, min_element
최대 또는 최소 원소를 찾는다.

reverse
원소의 순서를 뒤집는다.

replace
원소들을 새로운 값들로 대치한다.

rotate
가운데점을 중심으로 원소들을 순환시킨다.

partition
원소들을 두그룹으로 쪼갠다.

next_permutation
순열(permutation)을 생성한다.

random_shuffle
벡터내의 원소들을 임의로 섞는다.

count
조건을 만족하는 원소들의 갯수를 센다. 

accumulate
벡터로부터의 정보를 가지고 하나의 값을 만들어 낸다.

inner_product
두 벡터의 내적을 구한다.

equal
두벡터를 한쌍씩 비교하여 같은지를 검사한다.

lexicographical_compare 
사전식 비교 

transform
벡터에 변환을 적용한다.

partial_sum
값들의 부분합을 구한다.

adjacent_difference
이웃하는 값들의 차를 구한다.

for_each
각 원소들에 대해 함수를 수행한다.