서 론
STL은 반복자, 알고리즘, 함수 객체 등을 모아 놓은 것이죠, 하지만 대부분의 C++ 프로그래머들의 마음에 가장 멋진 것으로 늠름하게 서 있는 것은 컨.테.이.너.가 아닐까 합니다. 자바의 자료구조를 부러워하고 C++ 타입의 배열을 보면은 한숨아닌 한숨을 쉬다가 STL 컨테이너를 접한 사람들은 한 마디로 압도 당할 수밖에는 없습니다.
- 크기를 지정해 주지 않고도 알아서 늘어나고( 혹은 줄어들고), 내부에 들어 있는 객체의 개수도 추적해 주고, 메모리 관리까지 알아서 해주니 말이죠. 요소의 타입만 정해주면 어떤 데이터든 조작할 수 있는 Template의 특징을 그대로 가지면서, 데이터 조작에 소요되는 알고리즘적인 복잡도까지 미리 보장해 주어, 프로그래밍의 재미를 한층 높여주기 때문이라 할 수 있습니다.
본 론
여러분은 컨테이너가 다양하게 준비되어 있고, 이들을 입맛에 맞게 쓸 수 있다는 것을 알겠지만, 과연 다양한 입맛에 어떻게 정의를 해야되는지 난감해 할 수 있습니다. 이러한 일로 정리를 해보는것도 좋을 것 같아서 다음과 같이 정리를 통해서 정리하는 시간을 가지는 것도 중요하리라 생각합니다.
- 표준 STL 시퀸스( Sequence ) 컨테이너 : vector, string, deque, list.
- 표준 STL 연관( associative ) 컨테이너 : set, multiset, map, multimap
- 비표준 시퀸스 컨테이너 : slist와 rope가 있습니다. slist는 단이 ㄹ연결 리스트 이고, rope는 대용량 string입니다.( 대용량 "문자열"이란 이야기 이죠 ). 비표준컨테이너에 대해서는 다음에 정리를 통해서 알아보도록 하겠습니다.
- 비표준 연관 컨테이너 : hash_set, hash_multiset, hash_map, hash_multimap이 여기에 해당 됩니다. 표준 연관 컨테이너를 확정하여 해쉬 테이블을 쓰 수 있도록 한변형 클래스가 꽤 많이 나와 있습니다. 이 또한 다음에 정리를 통해 알아보도록 하겠습니다.
- string 대신 사용되는 vector<char> : 간혹 이렇게 쓰면 괜찮을 때가 있는데, 이 또한 다음에 정리하는 시간을 가져서 상세히 나열해보도록 하겠습니다.
- 표준 연관 컨테이너 대신 사용되는 vector : vector 가 수행 속도나 크기 면에서 표준 연관 컨테이너보다 낳은 경우도 있습니다.
- STL에 속하지 않는 표준 컨테이너 : 배열 ( C++ ), bitset, valarray, stack, queue, priority_queue가 여기에 해당됩니다.
주어진 상황에 가장 적합한 놈을 선택하는 일에 대해서 많은 사항들을 무시하는 것 같습니다. 심지어 표준안조차도 vector, deque, list 중의 선택 기준을 제공하는 것만으로 끝입니다.
vector, list, deque는 각자의 계산 복잡도를 제공하기 때문에 이를 고려하여 사용해야 한다. vector는 기본적으로 사용되는 시퀸스이고, list는 시퀸스는 중간에 빈번한 삽입, 삭제가 수행될 필요가 있는 경우에 사용이 된다. deque는 대부분의 삽입과 삭제가 시퀸스의 앞과 끝에서 일어나는 경우에 사용되는 자료구조입니다.
연속 메모리 ( contiquous-memory ) [ 배열 기반 컨테이너 array-based container ]
동적 할당된 하나 이상 - 대개 하나-의 메모리 단위( chunk)에다가 데이터 요소를 저장해 두는 컨테이너 입니다. 각 메모리 단위는 하나 이상의 요소를 담고 있습니다. 새 요소가 삽입되거나 이미 있던 요소가 지워지면 ( erase ), 같은 메모리 단위에 있던 다른 요소들은 앞 혹은 뒤로 밀려 나면서 새 요소가 삽입될 공간을 만들든지, 지워진 공간을 메웁니다. 이러한 "밀어내기" 때문에 수행 성능의 발목을 잡을 수 있죠, 예외 안전성 ( exception safety ) 에도 영향을 미칩니다. 표준 연속 메모리 컨테이너는 vector, string, deque가 있습니다. 비표준 컨테이너인 rope역시 연속 메모리 컨테이너에 속합니다.
노드 기반 ( node-based )
동적 할당된 하나의 메모리 단위에다가 하나의 요소만을 저장을 합니다. 컨테이너 요소를 삽입 or 삭제시 노드의 포인터만이 영향을 받지, 노드의 내용은 그대로 존재합니다. 따라서 삭제나 삽입이 일어났다고 해도 나머지 요소들이 밀려난다든지 하는 일은 존재하지 않습니다. 연결 리스트를 나타내는 컨테이너, 즉 list나 slist가 노드 기반이고, 표준 연관 컨테이너 모두가 노드 기반입니다. ( 이것들은 전형적으로 균형 트리( balanced tree ) 로 구현되죠.
결 론
- 컨테이너 아무 위치에 요소가 삽입이 가능한가요?
▶ 시퀸스 컨테이너가 가능하며, 연관 컨테이너는 불가능합니다. 위에서 언급했듯이 list or slist , 앞 뒤로는 deque
- 컨테이너 내의 요소들의 순서 결정에 직접관연하나여?
▶ 그렇지 않을 경우는 hash 컨테이너가 가장 괜찮을 것 같습니다. dictionary 로 되어 있기 때문에 쉽게 접근이 가능합니다.
- 표준 C++에 포함된 컨테이너를 사용해야 하나요?
▶ 그런 경우에는 해쉬 컨테이너를 사용합니다. 비 표준은 사용할 수 없게 되겠죠
- 어떤 타입의 반복자가 필요한가요?
▶ 임의 접근 반복자이어야 한다면 선택의 폭은 vector, deque, string으로 좁아지내요, 혹 양 방향인 경우에는 slit가 가능합니다.
- 요소 삽입이나 삭제시 다른 컨테이너 요소들이 밀려나는 일이 없어야 한다면요?
▶ 이런 경우에는 연속 메모리 컨테이너를 손을 대서는 안된다는 점입니다. 즉 노드 기반( node-based ) 컨테이너를 사용해야 합니다.
- 컨터이너 내의 데이터가 C의 데이터 타입과 메모리 배열 구조적으로 호환이 되어야 하나요?
▶ 이 때는 vector만이 가능합니다.
- 탐색 속도가 가능 중요한 관심인데요?
▶ 그렇다면 해쉬 컨테이너를 참조하시면 될듯 합니다. 정렬된 vector, 그리고 표준 연관 컨테이너 중 하나를 선택하시것이 맞을 것 같습니다.
- 컨테이너의 참조 카운팅이 신경 쓰인다면?
▶ 그렇다면 string 가까이에는 가지 않는 것이 좋습니다. 많은 string 코드가 참조 카운팅이 되도록 구현이 되어 있기때문입니다. 문자열을 나타날 때는 vector<char>
- 삽입과 삭제 동작이 트랜잭션적인 의미를 가지고 이루어졌으면 하나요?
▶ 트랜잭션 [ 문제가 발생시 ( roll back ) ]을 고려한다면 삽이이 려러 개의 요소에 대해 이루어져야 할 list를 선택합니다. 그 요구를 만족할 수 있는 유일한 STL 표준 컨테이너입니다. 트랜잭션적인 동작은 코드에 예외 안전성을 추가하고자 하는 프로그래머에게 대단히 중요한 특징입니다.
'프로그램언어 > Effective STL' 카테고리의 다른 글
| 항목3 : 복사는 컨테이너 안의 객체에 맞게 비용은 최소화하며, 동작은 정확하게 하자. (0) | 2008.08.19 |
|---|---|
| [ STL ]컨테이너에 독립적인( container-independent ) 코드 라는 환상을 조심하자. (0) | 2008.08.14 |