C++ 자료구조(STL)

array

- 배열

자료형 이름[크기]

 

vector

- 동적으로 요소를 할당할 수 있는 동적 배열

- 중복 허용

vector<자료형>

시간복잡도: 탐색 O(1)

 

stack

- 가장 마지막에 들어가는 원소가 가장 먼저 나오는 LIFO 자료구조

stack<자료형>

시간복잡도: 탐색  O(n)

 

queue

- 가장 먼저 들어간 원소가 가장 먼저 나오는 FIFO 자료구조

queue<자료형>

시간복잡도: 탐색 O(n)

 

prority_queue

- 우선순위가 높은요소가 낮은 요소보다 먼저 제공되는 자료구조

prority_queue<자료형>

 

deque

- 스케줄링에서 많이 사용

- 자원을 효율적으로 사용하기 위해 자원 사용 순서를 결정짓는 작업

시간복잡도 : 탐색 O(n)

 

Set

- 숫자든 문자든 중복을 없엔다.

- 삽입하는 순서에 상관없이 정렬되서 입력이 된다.

균형 이진트리

Map

- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조

- 해시 테이블 구현 시 사용

(중복을 허용하지 않음)

map<key,value>

 

시간복잡도 탐색/삽입/삭제O(log n)

 

pair<자료형, 자료형> : first, second의 형태

ex)vector<pair<int,int>> v; v.begin().first, v.begin().second

 

※ iterator -> 포인터 (배열요소를 가르키는)

ex) vector<int>::iterator biter = a.begin(); vector::iterator eiter = a.end();