적재적소 알맞은 컨테이너(effective STL 01)

종류를 알아보자.

Sequence Container : vector, string, deque, list

Associative Container : set, multiset, map, multimap

비표준 Sequence : slist(single linked list), rope(대용량 string).

비표준 Associative Constainer : hash_set, hash_multiset, hash_map, hash_multimap.

String 대신 사용되는 vector<char> : 간혹 이렇게 쓰면 괜찮을 때가 있다.

표준 연관 컨테이너 대신 사용되는 vector : vector가 수행 속도나 크기 면에서 표준 연관 컨테이너보다 더 나은 경우가 있다.

STL에 속하지 않는 표준 컨테이너 : 배열(C++ 배열), bitset, valarray, stack, queue, priority_queue.

백터, 리스트, 덱은 각자의 시간 복잡도를 제공한다. 

백터 : 기본적으로 사용되는 시퀀스.

리스트 : 시퀀스의 중간에 비번한 삽입, 삭제가 수행될 필요가 있을 때 사용한다.

덱 : 대부분의 삽입과 삭제가 시퀀스의 앞과 끝에서 일어날 경우 사용한다.

* 항 이펙티브 STL 날 가져. 이렇게 쓰는거구나!

STL의 컨테이너는 연속 메모리(contiquous-memory) 컨테이너와 

노드 기반(node-based) 컨테이너로 나눌 수 있다.

연속 메모리 컨테이너

- 동적 할당된 하나 이상의 메모리 단위(Chunk)에다 데이터 요소를 저장해 두는 컨테이너.

- 삽입과 삭제가 일어났을 시, 같은 메모리 단위에서 있던 다른 요소들이 압 혹은 뒤로 밀려나 공간을 만들던지 메운다.

- 수행 성능의 발목을 잡을 수 있다.

- 예외 안전성에도 영향을 미친다.

- vector, string, deque가 있다. +비표준 컨테이너 rope.

노드 기반 컨테이너

- 동적 할당된 하나의 메모리 단위에다가 하나의 요소만을 저장한다.

- 요소를 삽입, 삭제 했을 시, 노드의 포인터만이 영향을 받는다.

- list, slist 노드 기반. 전형적으로 균형(balanced tree)로 구현되어 있다.

 

어떤 상황에서 어떤 컨테이너를 쓰면 좋나요?

컨테이너의 아무 위치에 요소를 삽입?	시퀀스 컨테이너
컨테이너 내의 요소들의 순서 결정에 직접 관여하고 싶다?	YES - 해쉬 컨테이너는 피하라 NO - 해쉬 컨테이너
표준 C++에 포함된 컨테이너를 사용해야 한다면?	해쉬 컨테이너, slist, rope는 쓸 수 없다!!
어떤 타입의 반복자가 필요한가?	임의 접근 반복자 - vector, deque, string로 좁아지고 rope도 고려해 볼 수 있다. 양방향 반복자 - slist와 해쉬 컨테이너는 쓸 수 없다.
요소 삽입이나 삭제시 다른 컨테이너 요소들이 밀려나는 일이 없어야 한다!	절대! 연속 메모리 컨테이너는 사용하면 안된다.
컨테이너 내의 데이터가 C의 데이터 타입과 메모리 배열 구조적으로 호환되어야 한다?	오직 vector
탐색 속도가 중요	해쉬 컨테이너, 정렬된 백터, 표준 연관 컨테이너. 이 순서대로 고려하기.
컨테이너의 참조 카운팅이 신경쓰인다?	string는 사용하지 않는것이 좋다. 많은 string 코드가 참조 카운팅이 되도록 구현되어있다. rope도 피하라. rope는 확실한 참조 카운팅 기반이기 때문에. 이럴땐 vector<char>도 고려.
삽입과 삭제 동작이 트랜젝션처럼 동작할때.	list(이를 만족하는 유일한 STL 표준 컨테이너)
반복자, 포인터, 참조자가 무효화가 덜 일어나게 하려면?	노드 기반 컨테이너 사용. 연속 메모리 컨테이너는 재할당이 빈번히 일어나기 때문에 반복자나 포인터, 참조자가 무효화 되기 쉽다.
임의 접근 반복자를 지원하는 시퀀스 컨테이너, 요소 삭제가 일어나지 않고 요소 삽입이 컨테이너의 끝에만 일어나는 한, 포인터와 참조자가 무효화되지 않는 것이 필요한 경우?	deque가 정답.