STL Container 선택

표준 STL은 기본적으로 Homogeneous Collection만을 지원한다. 즉 같은 타입의 Object만을 저장할 수 있다.

일단 크기를 예상할 수 있다면 array 가 가장 좋다. 객체를 Access time이나 객체의 추가 삭제가 쉽고 가장 빠르다.

그러나 array를 사용하기 어려운 경우에 적당한 STL container를 찾아보자.

Containment Class	Container Type		Insert/Delete		Access
Vector	Sequencial	Dynamic Array 데이타 억세스가 많고 데이타의 추가가 뒤에서 일어날때	O(1) 임의지점 O(N-p)		O(1)
List	Sequencial	Binary Linked List 데이타의 추가 삭제가 빈번하고 접근하는 일이 적을 때	O(1)		O(N) or O(N/2)
Queue	Sequencial	First In First Out 의 객체 입출력이 있을 때만 사용		O(1)    N/A
Deque	Container Adapter	양방향 Queue (비추) Vector와 비슷한 구조 임의의 객체 접근이 느리다.		O(1)    O(1)
Stack	Container Adapter	Last In First Out 의 객체 입출력이 있을 때만 사용		O(1)    N/A
Set/Multiset	Sorted Associative Container Adapter	정렬된 자료구조 중복을 허용할 때는 Multiset 사용.		Vector<set<List    List <set< Vector
Map/Multimap	Sorted Associated Container Adapter	Key값에 의해 정렬된 자료구조를 갖는다. 중복을 허용할 때는 Multimap 사용.		Vector<set<List    List <set< Vector

 

이외에 bitset도 일반적인 Container는 아니지만 Container로 동작을 한다. 다만
insert/delete 같은 메소드가 정의되지 않고 iterator 도 지원되지 않는다.
vector나 array에 가깝다.

String도 기술적으로 보면 character의 vector 라고 볼 수 있다. 따라서 vector의 알고리즘들이 부분적으로 적용가능하다.

JAVA에서 보면 hash set hash map 이런 것들이 지원되는 데 C++의 표준에서는 지원되지 않고 C++11에서 지원이 된다.