블로그 이미지
Every unexpected event is a path to learning for you.

카테고리

분류 전체보기 (2731)
Unity3D (814)
Programming (474)
Server (33)
Unreal (4)
Gamebryo (56)
Tip & Tech (228)
협업 (57)
3DS Max (3)
Game (12)
Utility (136)
Etc (96)
Link (32)
Portfolio (19)
Subject (90)
iOS,OSX (51)
Android (14)
Linux (5)
잉여 프로젝트 (2)
게임이야기 (3)
Memories (20)
Interest (38)
Thinking (38)
한글 (30)
PaperCraft (5)
Animation (408)
Wallpaper (2)
재테크 (18)
Exercise (3)
나만의 맛집 (3)
냥이 (10)
육아 (16)
Total
Today
Yesterday
03-30 00:00

'컨테이너 조합'에 해당되는 글 1건

  1. 2010.03.21 STL Container 조합하기

STL 에서 하나의 Container를 선택하는 방법은 간단합니다.

 

  • vector – 맨 뒤에만 추가할 경우 순차 검색에 유리
  • dequeue – 앞 뒤로 추가할 경우 및 순차 검색에 유리
  • map – 검색이 필요할 경우 유리
  • list – 데이터의 삽입과 삭제가 빈번할 경우 유리

와 같은 식으로 간단하게 선택할 수 있습니다.

하지만가끔가다 보면 위에 Container 의 특징을 하나 이상 만족해야 할 경우가 있습니다특히 검색도 빨라야 하면서초기에 주어진 순서를 그대로 유지해야 하는 경우가 그렇습니다.

간단하게 생각하면 map 와 vector 를 같이 사용하면 되지 않나 싶은데요

몇 가지 고려해야 할 경우가 있습니다.

우선 설명을 더 진행하기 전에 예제에서 사용할 간단한 더미 구조체를 하나 선언하겠습니다단순 설명을 위한 자료구조이니 구조체는 신경 쓰지 말아 주세요. ~


struct DATA

{

           string sKey;

           char szDummy[20];

           int nDummy;

};

 

1.     vector  map 의 조합

먼저 생각할 수 있는 가장 흔한 방법입니다순차 검색을 위해 데이터는 vector 에 보관하고, vector 내의 데이터 인덱스를map으로 관리하는 방법인데요

코드를 나타내면 아래처럼 생각할 수 있습니다.


vector<DATA> m_vtData;

map<string, vector<DATA>::iterator> m_mapVtData;


데이터를 넣어 줘야겠지요아래처럼 vector  DATA 를 넣으면서 map 에는 vector 의 iterator 값을 넣어줘 봤습니다.

bool CstlcontainerDlg::InitData()

{

           DATA data;

           char szBuf[10];

           for (int i = 0 ; i < 1000; i++)

           {

                     sprintf_s(szBuf, sizeof(szBuf), "%03d", i);

                     data.sKey = szBuf;

                     data.nDummy  = i;

                     strcpy_s(data.szDummy, sizeof(data.szDummy), szBuf);

                     m_vtData.push_back(data);

                     vector<DATA>::iterator it = m_vtData.end();

                     it--;

                     m_mapVtData.insert(make_pair(data.sKey, it));

           }

 

           return true;

}

 


이 코드가 잘 작동하는지 아래처럼 검증해 볼 수 있습니다.


void CstlcontainerDlg::OnBnClickedButton2()

{

           // TODO: Add your control notification handler code here

           map<string, vector<DATA>::iterator>::iterator it = m_mapVtData.begin();

           map<string, vector<DATA>::iterator>::iterator itEnd = m_mapVtData.end();

           for (; it != itEnd; it++)

           {

                     TRACE("key Value -> %s\n", it->second->sKey.c_str());

           }

}


잘 작동할까요이미 눈치 채셨겠지만 이 방법은 프로그램이 바로 죽습니다. vector 에서는 iterator 값이 container 의 사이즈가 증가할 때 완전히 달라질 수가 있기 때문에 위 예제와 같이 vector  push_back 을 통해 계속 데이터를 추가하면서 그때 마다 iterator를 저장해서 사용할 경우 아무 의미 없는 데이터를 가리키게 되어 결국 프로그램이 죽게 됩니다.

프로그램을 죽지 않게 하기 위해서는 vector 에 모든 데이터를 넣은 후에, map  iterator 를 넣어주는 방법으로 하면 됩니다.


bool CstlcontainerDlg::InitData()

{

           DATA data;

           char szBuf[10];

           // 우선vector 에아무값이나넣습니다.

           for (int i = 0 ; i < 1000; i++)

           {

                     sprintf_s(szBuf, sizeof(szBuf), "%03d", i);

                     data.sKey = szBuf;

                     data.nDummy  = i;

                     strcpy_s(data.szDummy, sizeof(data.szDummy), szBuf);

                     m_vtData.push_back(data);

           }

          

           // 채워진vector iterator map 에저장합니다.

           vector<DATA>::iterator it = m_vtData.begin();

           vector<DATA>::iterator itEnd = m_vtData.end();

           for (; it != itEnd; ++it)

           {

                     m_mapVtData.insert(make_pair(it->sKey, it));

           }

           return true;

}


만약데이터가 초기에 로딩된 후에 더 이상 삽입이나 삭제가 되지 않을 경우는 이 방법으로 충분합니다하지만 데이터를 더 추가해야 하거나삭제할 경우 모든 map  iterator 를 다시 갱신해야 하는 오버헤더가 따릅니다.


2.     list  map 의 조합

제가 생각하는 가장 좋은 조합입니다.

list  vector 와 달리 모든 iterator 가 삽입삭제에 무관하게 유지 되기 때문에 list::iterator 를 이용하면 훌륭한 데이터 위치 추적이 가능합니다.

이번에는 list  list 의 iterator 를 이용하는 샘플을 만들어 보겠습니다.


list<DATA> m_lstData;

map<string, list<DATA>::iterator> m_mapLstData;


초기 데이터를 넣는 방법은 vector  map 에서와 같습니다아래처럼 짝퉁 키를 만들어서 리스트에 넣고리스트의 iterator를 구해서 map 에 추가했습니다.


bool CstlcontainerDlg::InitData()

{

           DATA data;

           char szBuf[10];

           for (int i = 0 ; i < 1000; i++)

           {

                     sprintf_s(szBuf, sizeof(szBuf), "%03d", i);

                     data.sKey = szBuf;

                     data.nDummy  = i;

                     strcpy_s(data.szDummy, sizeof(data.szDummy), szBuf);

 

                     m_lstData.push_back(data);

                     list<DATA>::iterator itList = m_lstData.end();

                     itList--;

                     m_mapLstData.insert(make_pair(data.sKey, itList));

           }

           return true;

}


이제 map 으로 순차 검색했을 때 list 의 데이터가 제대로 들어 있는지 테스트 코드를 돌려 봤습니다.


void CstlcontainerDlg::OnBnClickedButton3()

{

           // TODO: Add your control notification handler code here

           map<string, list<DATA>::iterator>::iterator it = m_mapLstData.begin();

           map<string, list<DATA>::iterator>::iterator itEnd = m_mapLstData.end();

           for (; it != itEnd; it++)

           {

                     TRACE("key Value -> %s\n", it->second->sKey.c_str());

           }

}


문제 없이 잘 작동합니다 ^^;

이제 리스트에서 키 값이 “887” 인 항목을 지우려고 합니다키 값 검색을 빠르게 하기 위해 당연히 map 으로 검색하고검색된 데이터는 map 과 리스트에서 모두 제거했습니다.


void CstlcontainerDlg::OnBnClickedButton4()

{

           // TODO: Add your control notification handler code here

           string sKey = "887";

           map<string, list<DATA>::iterator>::iterator it = m_mapLstData.find(sKey);

           if (it == m_mapLstData.end())

                     return;

           TRACE("key Value -> %s\n", it->second->sKey.c_str());

           m_lstData.erase(it->second);

           m_mapLstData.erase(it);

 

           it = m_mapLstData.begin();

           map<string, list<DATA>::iterator>::iterator itEnd = m_mapLstData.end();

           for (; it != itEnd; it++)

           {

                     TRACE("key Value -> %s\n", it->second->sKey.c_str());

           }

           TRACE("\nLIST SIZE->%d, MAP<LIST> SIZE -> %d\n"       m_lstData.size(), m_mapLstData.size());

 

}


역시 잘 작동합니다리스트 순차조회의 경우 아시는 것처럼 vector<> 의 순차 검색보다 분명 느린 단점이 있습니다하지만 깨지지 않는 iterator 를 통해 map 과 함께 사용될 경우 안정성을 보장받을 수 있는 장점이 있습니다.

 

3.     기타 조합

그 외에도 데이터를 new 한 다음 그 포인트 값을 vector  map 에 보관시켜 검색과 순차조회를 하는 방법도 물론 있습니다.


vector<DATA*> m_vtData;

map<string, DATA*> m_mapVtData;


이 경우 단점은 new 와 delete 의 책임이 프로그래머가 가지게 된다는 단점이 있고데이터를 삭제해야 할 경우에는 vector의 모든 데이터를 뒤져야 하기 때문에 삭제가 필요한 경우에는 적합하지 않습니다.

 

이상 간단하게 STL 의 컨테이너 선택에 대해 조금 생각해 본 내용인데요또 다른 좋은 방법이 있을지도 모르겠습니다고수님들 혹시 이 글을 읽으신다면 조언 부탁 드리겠습니다. ^^;



반응형

'Programming > STL' 카테고리의 다른 글

C++ STL int -> string, string -> int 로 변환하기  (1) 2010.04.27
괜찮은 참고 사이트  (0) 2010.04.20
effective_stl-hermet  (0) 2010.04.08
STL  (0) 2010.03.22
About STL : C++ STL 프로그래밍  (0) 2010.03.21
Posted by blueasa
, |