C++) Container비교

특징은 무엇이고 문제를 풀고자 할 때 어떤 컨테이너를 선택해야 할까?

 

순차 컨테이너

• vector
  • 임의 접근 가능, 순차 접근 가능
  • 뒤에서 삽입, 삭제가 빠름
  • 크기 변경 가능
  • 각 요소를 메모리 상 연속적으로 저장
  • 메모리 동적으로 할당 (내부 capacity가 고갈될 시 전체 메모리 크기만큼 재할당 발생)

• deque 
  • 임의 접근 가능 
  • 앞과 뒤에서 삽입과 삭제 빠름
  • 크기 변경 가능
  • Vector와 다르게 각 요소들이 메모리 상에 연속적으로 저장되지 않고, 각 node는 개별적인 메모리를 할당
  • 내부 capacity가 고갈될 시 일정 크기를 가지는 chunk 단위로 확장됨( 저장 원소가 많고 메모리 할당량이 큰 경우 Vector에 비해 확장 비용이 절감되지만, 컨테이너 처음부터 끝까지 연속 메모리 공간이 아니므로, Vector에서 가능했던 원소들 간 포인터 연산 불가능)
• list 
  • 특정 위치에 접근이 불가능하지만, 위치에 상관없이 삽입, 삭제가 빠름 (상수 복잡도)
  • 특정 원소에 접근하려면  Forward/Reverse 순회만 가능 (선형 복잡도)
  • 원소들간 상호 연결 정보를 위해 추가적인 메모리가 사용됨 (doubly-linked list로 구현 됨)

Sequence Container	시간 복잡도
	Random Access	찾기	node 삽입/ 삭제
Vector	O(1)	O(n)	O(n) (맨 뒤 : O(1))
Deque	O(1)	O(n)	O(n) (맨 앞/뒤 : O(1))
List	지원 X	O(n)	O(1)

연관 컨테이너

• set
  • red_black tree 구조
  • 값들에 순서가 유지 되어야 한다면
  • key의 집합
  • 원소들을 순서대로 관리하며 소속검사, 삽입 ,삭제 빠름
  • 삽입시 자동 정렬 (default : 오름차순정렬)
• multiset
  • 중복을 허용하는 set
• map
  • red_black tree 구조
  • 키 - 값 
  • 삽입시 자동 정렬 (default : 오름차순정렬)
  • value값 정렬하고 싶을 시, vector<Pair<,>> 복사 후 정렬 알고리즘 사용
• multimap
  • 중복을 허용하는 map 

정렬되지않은 map,set : unordered_map / unordered_multimap / unordered_set / unordered_multiset

Associative Container	시간 복잡도
	Random Access	찾기	node 삽입/ 삭제
set	지원 X	O(log n)	O(log n)
map	지원 X	O(log n)	O(log n)

 

컨테이너 어댑터 (반복자를 지원하지 않아 STL 알고리즘을 이용할 수 없습니다.)

• statck 
  • top에서만 삽입, 삭제 가능
• queue
  • 삽입은 뒤쪽에서, 삭제는 앞쪽에서
• priority_queue 
  • 가장 큰 값(or 가장 작은 값)을 찾아 제거하는 연산이 빈번하면
  • 가장 큰 값(or 가장 작은 값)의 접근과 삭제가 빠름

Container Adaptors	시간 복잡도
	Random Access	찾기	node 삽입/ 삭제
stack			amortized O(1)
queue			amortized O(1)
priority_queue			O(log n)