queue/priority_queue/map/set 특징 기록

queue

선입선출. 내부적으로 deque로 구현.

 

priority_queue

우선순위가 높은것이 항상 선출.

힙(heap) 구조.  = ["완전 이진 트리 구조", "부모가 항상 우선순위 높음", 배열기반]

 

내부 구조 배열 지정 차이

1. vector:
   •  장점:
     • std::vector는 연속된 메모리 블록을 사용하므로 데이터 접근이 빠르다.
     • 요소들의 삽입 및 삭제가 빠르게 수행되는 경우에 효율적이다.
   • 단점:
     • 용량이 변경될 때마다 데이터 복사 및 재할당이 발생할 수 있다.
     • 요소 삽입 및 삭제 작업은 일반적으로 상수 시간이 아닌 로그 시간이 걸릴 수 있다.
2. deque:
   • 장점:
     • std::deque는 양방향 큐 구조로 데이터 삽입 및 삭제가 빠르다.
     • 큐의 크기가 커지면서 재할당이 발생해도 요소들의 재배치 없이 요소 삽입이 가능하다.
   • 단점:
     • std::deque는 메모리 사용 및 관리 측면에서 약간 더 복잡할 수 있다.
     • 데이터의 접근 시점에 따라 캐시 효율성이 std::vector에 비해 약간 떨어질 수 있다.

 

 

map/set

균형 이진 탐색 트리 구조.(레드 블랙 트리?)

[왼쪽 자식 < 루트 < 오른쪽 자식] 구조이다. (왼쪽 작고, 오른쪽 크다)

key 기준 less/greater 정렬만 가능.