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

출처 : http://eslife.tistory.com/entry/CSTL-Container-조합하기