STL 컨테이너 선택하기

출처: http://oopsla.snu.ac.kr/~sjjung/stl/sel_2116.htm

다음 질문들은 특정 문제를 풀고자 할 때 어떤 종류의 컨테이너를 선택하는 것이 좋은가에 관한 몇가지 선택 기준을 제시하고 있다.
콜렉션내의 값들을 어떤 방식으로 접근하는가?

임의접근이 필요하다면, vector와 deque를 사용하라. 순차접근만으로 충분하다면, 다른 컨테이너를 써도 무방하다.

콜렉션내의 값들에 순서를 매길 것인가?

값들이 나열되는 방식에는 여러가지가 있다. 컨테이너가 유지되는 동안 계속 순서가 유지되어야 한다면, set을 선택해야 한다. set에 삽입을 하면 자동적으로 순서에 맞게 놓여진다. 반면에, 순서가 어느 한시점에서만 중요시된다면, list나 vector에 값들을 삽입하고, 적절한 때에 해당 컨테이너를 정렬을 하는 것이 더 수월하다. 만약에 데이터구조 내에서 유지되는 값들의 순서가 삽입하는 순서에 관계가 있다면, stack이나 queue또는 list가 최상의 선택이 될 것이다.

실행중에 데이터 구조의 크기가 광범위하게 변하는가?

그렇다면, list나 set를 선택하는 것이 가장 좋다. vector나 deque은 콜렉션으로부터 원소들을 제거한 뒤에도 커다란 버퍼를 계속 유지하고 있다. 만약에, 콜렉션의 크기가 상대적으로 고정되어 있다면, vector나 deque가 같은 수의 원소를 지니고 있는 list나 set보다는 적은 메모리를 사용한다.

콜렉션의 크기를 추정할 수 있는가?

vector는 원하는 크기의 메모리 블럭을 미리 할당받을 수 있다(reserve() 멤버함수를 사용). 이는 다른 컨테이너에서는 제공되지 않은 기능이다.

어떤 값이 콜렉션내에 포함되어 있는지를 자주 확인하는가?

만약에 그렇다면, set이나 map을 선택하는 것이 좋겠다. set이나 map에서는 어떤 값이 컨테이너에 속해 있는지를 검사하는 것이 매우 빠르지만, 다른 종류의 콜렉션에서는 이를 검사하기 위해서 컨테이너에 저장된 모든 원소들을 일일이 비교해야 한다.

콜렉션에 대해 인덱싱이 가능한가? 다시말해, 콜렉션을 키와 값의 쌍으로 생각할 수 있는가?

키들이 0과 어떤 상한선 사이의 정수값이라면, vector와 deque를 선택해야 한다. 반면에, 키값들이 어떤 순서가 있는 데이터형이라면(문자나 문자열 또는 사용자 정의 타입과 같은) map을 사용한다.

값들간에 서로 연관성이 있는가?

표준 라이브러리가 제공하는 컨테이너에 속한 모든 값들이 다른 값과 같은지를 비교할 수 있어야 한다. 하지만, 모든 컨테이너가 less-than 연산자를 제공할 필요는 없다. 그러나, less-than 연산자를 사용해서는 순서가 유지될 수 없는 값들은 set이나 map에 저장하면 안된다.

콜렉션으로부터 가장 큰 값을 찾아서 제거하는 연산이 자주 일어나는가?

그렇다면, priority_queue가 최선의 컨테이너이다.

데이터 구조의 어느 위치로 값들이 삽입되고 제거되는가?

중간쯤에서 값들이 삽입되고 제거된다면, list가 최선의 선택이다. 값들이 앞쪽에만 삽입된다면, deque나 list가 더 좋겠고, 끝에서만 삽입과 삭제가 이루어진다면, stack이나 queue가 좋을 것이다.

두개 이상의 수열을 하나로 합치는 일이 자주 일어나는 연산인가?

그렇다면, set이나 list가 좋은 선택이 될 것이다. 이 둘중에 어느 것을 선택할 지는 순서가 유지되는가의 여부에 따라 결정하면 된다. 두개의 set을 합치는 것은 매우 효율적인 연산이다. 콜렉션의 순서가 유지되지 않고, list가 제공하는 효율적인 splice() 멤버함수를 사용하면, list를 선택하는 것이 좋겠다. 왜냐하면, 이 연산은 다른 컨테이너에서는 제공하지 않는 연산이기 때문이다.

대부분의 경우에 주어진 문제에 대해서 여러가지 컨테이너가 사용될 수 있는데, 그럴때는 실제 수행시간을 비교해서 어느 것이 나은가를 결정하는 것도 한 방법이 될 것이다.