본문 바로가기
개발/C C++

[C++]STL Container 조합하기

by esstory 2007. 11. 12.

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 의 컨테이너 선택에 대해 조금 생각해 본 내용인데요. 또 다른 좋은 방법이 있을지도 모르겠습니다. 고수님들 혹시 이 글을 읽으신다면 조언 부탁 드리겠습니다. ^^;



댓글