[ STL ]컨테이너에 독립적인( container-independent ) 코드 라는 환상을 조심하자.

서   론

STL은 일반화( generalization)에 기초를 두고 만든 프로그래밍 장치이면 언어입니다. 배열 [ array] 이란 데이터 집합은 컨테이너로 일반화되었고, 매개 변수를 통해 컨테이너에 담을 수 있는 데이터의 타입을 지정할 수 있도록 만들어졌습니다. 함수는 알고리즘으로 일반화되었고, 알고리즘에서 사용되는 반복자의 타입으로 매개 변수화 되었습니다.

  표준 연속 메모리 컨테이너는 임의 접근 반복자를 쓸 수 있도록 해주고, 이와 반대로 노드 기반 컨테이너는 push_front와 push_back을 지원하지만, 연관 컨테이너는 그렇지 않습니다. 연관 컨테이너에서는 로그 시간의 복잡도를 가진 low_bound, upper_bound, equal_range 함수를 쓸 수 있지만, 시퀸스 컨테이너를 지원하지 않습니다.



본   론

  화. 이렇게 좋은 개념인데 동참하지 않는 것이 참 이상하죠. 일반화교에 빠진 여러분은 스스로 사용할 컨테이너나 반복자, 알고리즘을 만들 때마다 이것을 염두에 둘 것입니다. 모든 컨테이너에 대해 미련을 두고 사용할 수 있도록 코드를 만듭니다. 예을 들면 vector를 쓰는 부분을 만들면서 언제든지 deque, list를 쓸 수 있는 여지를 남겨 둔다는 거죠 즉, 컨테이너에 독립적인( container-independent ) 코드를 작성하려고 기를 쓴다고 할 수 있습니다. 이러한 종류의 일반화는 의도는 좋지만 거의 항상 잘못된 이해에서 오는 행동이라 할 수 있습니다.
"컨테이너 독립적인 코드는 좋다!"라고 아무리 이야기를 해놓지만 스퀸스 컨테이너와 연관 컨테이너 양쪽에 대해서 동일하게 동작하는 소프트웨어를 만드는 일도 시도 자체가 무의미하다는 것을 바로 알 수 있습니다. 우선, 대다수의 맴버 함수들이 한쪽 부류의 컨테이너에만 치우쳐 들어 있습니다. 예를 들어, push_back과 push_front는 스퀸스 컨테이너에만 지원되고, count와 low_bound등은 연관 컨테이너에서만 지원이 됩니다.  insert나 erase등의 기본적인 함수는 (양쪽에 모두 존재합니다.) 시그너쳐나 동작 원리는 다릅니다. 시퀸스 컨테이너에 어떤 객체를 insert하면 삽입한 위치에 그 객체가 그대로 있지만, 연관 컨테이너는 자체의 정렬 방식에 맞게 그 객체를 이리 저리 옮겨 다니죠. erase는 또 어떻게 될까요? 반복자를 받아들이는 erase의 경우, 시퀸스 컨테이너에 대해 호출하면 반복자가 새로 반환되지만, 연관 컨테이너에 대해 호출하면 아무것도 반환되지 않습니다. ( 이것이 어떤 영향을 미치는 지는 다음에 설명을 하도록 하겠습니다. )

  가장 많이 사용하고 있는 시퀸스 컨테이너로는 vector, deque, list에 대해서만 쓸 수 있는 코드를 만드는 것입니다. 각 컨테이너의 공통된 특징만을 사용하도록 프로그래밍해야 한다는 이야기가 되죠. 이러면 reserve나 capacity등은 무용지물입니다. 왜냐하면 deque와 list에 제공하지 않는 것이기 때문이죠. list 때문에 operator[]도 쓰 수 없고, 양방향 반복자에 대해 동작하도록 코드를 제한시켜야 합니다. 임의 접근 반복자를 사용하는 알고리즘에는 손도 못 댄다는 결론이 나옵니다. sort, stable_sort, partial_sort, nth_element 등의 주옥같은 함수들을요.  이뿐이 아니죠 vector를 지원하기로 했기 때문에 push_front와 pop_front는 가볍게 탈락이며, vector와 deque 덕분에 splice와 멤버 함수 형태의 sort는 찍소리도 할 수 없습니다.

반복자, 포인터, 참조자를 무효화 시키는 방식이 컨테이너마다 다르다는 것입니다.

경우에 따라 수시로 컨테이너 타입을 바꿀 수밖에 없는 입장이라면, 변경을 조금 조금 용이하게 해주는 방법을 쓸 수 있습니다. 바로 "캡슐화"이지요, 가장 쉬운 방법은 컨테이너와 반복자 타입에 대해 typedef를 거는 것입니다. 즉 다음과 같이는 쓰지 말라는 예제이네요.

class Widget{....};
vector<Widget> vw;
Widget bestWidget;
....
vector<Widget>::iterator i = find(vw.begin(), vw.end(), bestWidget);
// bestWidget에 다가 어떤 값을 줍니다. bestWidget과 같은 값을 가진 Widget을 벡터에서 찾습니다.

다음과 같이 쓰는 것입니다.

class Widget{...};
typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer vw;
Widget bestWidget;
...
WCIterator  i = find( vw.begin(), vw.end(), bestWidget );

이렇게 하면 컨테이너 타입을 쉽게 변경 할 수 있습니다. 자주 필요한 작업이 커스텀 할당자를 붙인다든지 하면 편리하겠죠. ( 반복자/포인터/참조자 무효화 방식에 영향을 주지 않는 변경이죠)

class Widget{...};
template<typename T>
SpecialAllocator{....};
typedef vector<Widget, SpecialAllocation<Widget>> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer vw;
Widget bestWidget;
...
WCIterator i  = find( vw.begin(), vw.end(), bestWidget);
여기서 템플릿을 왜 사용하는지에 대해 이후에 정리하도록 하겠습니다.

typedef 를 사용한 캡슐화라고 해서 여러분의 감동이 적을지도 모르겠지만, 이것이 절약해 주는 작업량에 대해서는 고마워할 확률이 높습니다. 예를 들어 다음과 같은 개체 타입이 있다고 합시다.

map<stirng, vector<Widget>::iterator, CIStringCompare>
 //CIStringCompare는 "case-insensitive
// stirng compare" 의 약자입니다. 자세한 사항은 또 정리하도록 하겠습니다.

그리고 이 맵의 내부를 const_iterator를 사용해서 이동하고 싶다면, 아마 변수 선언문의 타입 이름이 이렇게 나와야 할 것입니다.

map<string, vector<Widget>::iterator, CIStringCompare>::const_iterator

결   론

게임을 만드는 프로그래머로서 너무 나도 많은 배운것을 알 수 있습니다. 데이터를 처리할 때 난감한 경우가 많이 발생하는데 어떻게 하면 효율적이고 빠르게 할 수 있는지에 대해서 고민이 상당히 많이 있습니다. 정리하였듯이 하나의 반복자만 사용하면 좋지만 상황에 따라서 다양하게 써야 될 부분들이 많이 있기 때문이죠. 한번도 고민을 해보고 더 효과적인 방법에 대해서 생각해 보아야 할 문제인것 같습니다.


Reference

ㅇ http://www.cplusplus.com/reference/stl/vector/capacity.html
ㅇ 이펙티브 STL