[STL] 컨테이너 종류

vector

동적 배열을 기반으로하는 컨테이너

동적 배열 기반이므로 인덱스 접근이 가능하다 (탐색이 좋다)

원소를 삽입할 경우 앞에서는 할 수 없으며, 뒤에서부터 삽입해 나간다.

중간 삽입 및 삭제 시에는 삽입공간의 확보, 삭제 공간의 활용을 위해

해당 인덱스 이후 모든 원소들을 포인터 이동해야한다. (선형 시간)

단, 맨 끝에서 삽입 및 삭제 시에는 확보 및 활용할 필요가 없다. (상수 시간)

동적 배열이므로 배열의 크기를 넘어서는 삽입의 시도가 있을 경우

배열의 재할당 및 복사가 발생한다.

또한 원소를 삭제한다 하여도 배열의 크기는 줄어들지 않는다.

 

-> 삽입 및 삭제 불리

-> 탐색이 용이

 

 

list

노드를 기반으로하는 컨테이너

더블 링크드 리스트로 구현이되어있다.

각 노드는 연속적인 메모리에 나열된 것이 아니라

메모리 여기 저기 나열되어 있지만 포인터로 각 노드를 연결하여

마치 연속된 메모리에 나열된 것처럼 보인다.

-> 인덱스 접근이 불가능하다.

원하는 원소를 탐색하기 위해서는 순차적으로 순회하여 원하는 원소를 찾아야한다.

-> 탐색이 불리하다.

중간 삽입 및 삭제 시에는 단순히 연결되어 있는 포인터의 해제 및 재 연결만 하면 되므로

연속된 메모리를 사용하는 vector보다 삽입 및 삭제가 유리하다.

또한, 한정적인 메모리를 사용하지 않기 떄문에 런타임 중 사용자가 원할떄

계속해서 노드를 추가해나갈 수 있다.

 

-> 삽입 및 삭제 용이

-> 탐색이 불리

 

 

map

map의 원소들은 key와 value로 한 쌍을 이룬다.

각 원소들은 삽입 시에 key값에 따라 자동 정렬이 된다.

정렬이 되기 떄문에 반복자를 통한 순회가 가능하다.

노드 기반 컨테이너들 중 유일하게 key값으로 임의 접근이 가능하다.

리소스 탐색 용으로 많이 쓰인다.

중복 key값은 허용하지 않는다