[ C++ ] STL 정리하기 1. 컨테이너의 종류와 선택팁

C++ 기초를 복습하고 나서 코딩테스트 문제를 풀다보면 직접 구현할수도 있지만 이미 구현되어있는 자료구조, 알고리즘을 불러오면 쉽다는걸 느꼈다..

 

처음에는 STL 왜쓰는지.. 그냥 직접 구현하면 되는거 아닌가 했더니 사용해보니 진짜 편하긴하다..

 

그래도 쓰기전에는 꼭 직접 모든것을 구현해보자... 어떻게 동작하고 어떤 원리인지는 알고 써야지..

 

---

STL에는 많은 컨테이너가 있다.  ( 자료구조라 생각하면 편함 )

• 표준 STL 시퀸스(sequence) 컨테이너: vector, string, deque, list.
• 표준 STL 연관(associative) 컨테이너: set, multiset, map, multimap.
• 비표준 시퀸스 컨테이너: slist(단일 연결 리스트), rope(대용량 string).
• 비표준 연관 컨테이너: hash_set, hash_multiset, hash_map, hash_multimap.
• STL에 속하지 않은 표준 컨테이너: 배열(C++ 배열), bitset, valarray, stack, queue, priority_queue. 
  

 

이렇게 많은것중 한가지만 알면 당연히 안된다.. 각각의 특징을 이해하고 언제 어떤것을 사용할지를 정리하는것이 이 글의 목표....   

 

우선, STL 컨테이너는 연속 메모리(continuous-memory) 컨테이너와 노드 기반(node-based) 컨테이너로 나눌 수 있다.

 

• 연속 메모리 컨테이너( 배열 기반 컨테이너 )
  동적 할당된 하나 이상( 대개 하나 )의 메모리 단위( chunk )에다가 데이터 요소를 저장해 두는 컨테이너입니다. 새 요소가 삽입되거나 이미 있던 요소가 지워지면(erase), 같은 메모리 단위에 있던 다른 요소들은 앞 혹은 뒤로 밀려나면서 새 요소가 삽입될 공간을 만들던지, 지워진 공간을 메웁니다. 이러한 "밀어내기" 때문에 수행 성능의 발목을 잡을 수 있고, 예외 안전성(exception safety)에도 영향을 미칩니다.
  여기에 속하는 컨테이너는 vector, string, deque입니다. 비표준 컨테이너인 rope 역시 연속 메모리 컨테이너입니다.

 

• 노드 기반 컨테이너
  동적 할당된 하나의 메모리 단위에다가 하나의 요소만을 저장합니다. 컨테이너 요소를 삽입 혹은 삭제했을 때 노드의 포인터만이 영향을 받지, 노드의 내용은 그대로입니다. 따라서, 삭제나 삽입이 일어났다고 해도 나머지 요소들이 밀려난다든지 하는 일이 없습니다.
  
  연결 리스트를 나타내는 컨테이너, 즉 list와 slist가 노드 기반이고, 표준 연관 컨테이너 모두가 노드 기반 입니다(이것들은 전형적으로 균형 트리(balanced tree)로 구현되어 있습니다).

 

• 이제는 "어떤 상황에 어떤 컨테이너를 쓰면 가장 좋을까?"에 관련된 문답을 수월하게 정리할 수 있을 것입니다.
  • 인덱스를 통한 요소 삽입 가능해야한다. -> 시퀀스 컨테이너
  • 요소들의 순서에 관심 없다 -> 해쉬 컨테이너
  • 반복자 타입에 대한 구분
    • 임의 접근 반복자 : vector, deque, string
    • 양방향 반복자 : slist와 해쉬 컨테이너는 쓸 수 없다
  • 요소 삽입 삭제시 다른 요소가 밀려나는일 없어야한다 : 연속메모리 컨테이터는 불가
  • C의 데이터 타입과 메모리 배열 구조적으로 호환되어야 한다 : vector 밖에 쓸 것이 없다.
  • 탐색 속도가 중요하다 : 해쉬 컨테이너, 정렬된 vector, 그리고 표준 연관 컨테이너
  • 컨테이너의 참조 카운팅이 신경 쓰이나요? 그렇다면 string 가까이에는 가지 않는 것이 좋습니다. 많은 string 코드가 참조 카운팅이 되도록 구현되어 있습니다. 이럴 때 vector<char>를 쓰는 것입니다.
  • 삽입 삭제가 안정적 : 노드 기반 컨테이너를 고려해 보시기 바랍니다.
  • 트랜잭션적인 삽입이 여러 개의 요소(범위로 주어집니다)에 대해 이루어져야 할 경우에는 list를 선택합니다. 
  • 반복자, 포인터, 참조자가 무효화(포인터가 가리키고 있던 메모리의 실제 내용이 없어지는 일을 뜻한다)되는 일을 최소화해야 하나요? 이런 경우에는 노드 기반 컨테이너를 사용하기 바랍니다. 노드 기반 컨테이너는 노드 삽입과 삭제가 일어나도 기존의 반복자나 포인터 혹은 참조자가 무효화되지 않기 때문입니다(가리키고 있는 요소를 삭제하지 않는 한 말이죠). 반대로 연속 메모리 컨테이너는 전체적인 메모리 재할당이 빈번하게 일어나기 때문에 반복자나 포인터, 참조자가 무효화되기 쉽습니다.
  • 임의 접근 반복자를 지원하는 시퀸스 컨테이너가 필요한데, 요소 삭제가 일어나지 않고 요소 삽입이 컨테이너의 끝에서만 일어나는 한, 포인터와 참조자가 무효화되지 않는 것이 필요한가요? 아주 특별한 경우이긴 하지만, 어쩌다 이런 경우를 만난다면 deque가 정답입니다. deque는 요소 삽입이 끝에서 일어날 때 반복자만 무효화되는 재미있는 컨테이너입니다(STL 컨테이너 중 포인터와 참조자를 무효화시키지 않고 반복자만 무효화되는 것은 deque가 유일합니다).

 

참조 : http://ajwmain.iptime.org/programming/book_summary/%5B02%5Deffective_stl/effective_stl.html#I04