[C++] STL container 간단 정리

vector, stack, queue, deque, priority_queue, list, iterator의 간단 정리입니다.

 

 

1. vector vs queue, stack (+ deque, priority_queue)

일단 벡터는 동적 “배열”이고, 나머지는 아니다.

-> 이에 따라 임의접근(배열처럼 접근 하는 방식)이 가능하고 아니고가 갈린다. 배열은 임의접근 가능하다.(like a[1], 그러나 예외도 존재 : deque)

 

2. stack vs queue

stack은 LIFO(책을 올리는 것과 유사), queue는 FIFO(= 줄을 서고 있는 것과 유사)

-> 즉 stack은 나중에 들어온 게 먼저 나가고, queue는 먼저 들어온 게 먼저 나간다.

 

3. deque

double ended – queue의 줄인 말

-> 양쪽에서 push, pop 가능한 자료 구조, 임의 접근이 가능한 것이 특이점이다.

 

4. priority_queue

힙이라고 생각하면 된다. 최소 힙과 최대 힙 또는 다른 기준으로 힙을 구현 할 수 있다.

->default값은 vector와 less이다.(최대힙)

 

5. list

링크드리스트이다. 더블링크드리스트가 구현되어 있다. 임의 접근이 불가능하다.

->iterator이 필요하다.

 

6. vector

- 동적 “배열”

- #include <vector> 사용

- namespace std 사용

- 형식 : vector<T>

- v.push_back(x) //뒤에 넣어줌

- v.pop_back(x) //뒤에 것을 빼줌

- v.begin() //첫번째 요소 리턴

- v.end()

- v.resize(size)

- v.size() //실제 유효한 요소의 개수

- v.max_size() // 벡터에 들어 갈수 있는 최대 개수 리턴

- v.capacity() // 요소를 담을 수 있는 공간의 개수

- v.empty() //비어있으면 true(=1) 리턴

- v.clear() //벡터를 아예 비워줌

 

7. stack

- 동적 자료형

- LIFO(책을 차곡차곡 올리는 모양)

- #include <stack> 사용

- namespace std 사용

- 형식 : stack<T>

- s.push(x)

- s.pop() //맨 위의 값 제거

- s.top() //맨 위의 값 return

- s.size()

- s.empty()

 

8. queue

- 동적 자료형

- FIFO(줄을 서는 모양)

- #include <queue> 사용

- namespace std 사용

- 형식 : queue<T>

- q.push()

- q.pop()

- q.front() // 앞의 값을 return, 스택은 s.top(뒤의 값, 즉 맨 위의 값 return)을 사용

- q.size()

- q.emtpy()

 

9. deque

- 동적 자료형 – 임의 접근이 가능

- 양쪽에서 입력 삭제 가능

- #include <deque> 사용

- namespace std 사용

- 형식 : deque<T>

- dq.push_back()

- dq.push_front()

- dq.pop_back()

- dq.pop_front()

- dq.front()

- dq.back()

- dq.size()

- dq.empty()

 

10. priority_queue

- 동적 자료형 – “힙”

- #include <queue> 사용

- namespace std 사용

- 형식 : priority_queue<int, vector<int>,less<int> > : 뒤의 두 개 인자는 생략 시 이것이default값이다.(최대힙)

- 최소 힙 선언 : priority_queue<int, vector<int>,greater<int> > (컴파일러 오류를 막기 위해 띄어써주자, greater는 functional헤더 파일에!)

- pq.push()

- pq.pop()

- pq.top()

- pq.empty()

- pq.size()

 

11. list

- 동적 자료형

- #include <list> 사용

- namespace std 사용

- 형식 : list<T>

- L.insert(iterator, x)

- L.erase(iterator, x)

- L.push_back()

- L.push_front()

- L.pop_back()

- L.pop_front()

- L.size()

- L.clear()

- L.sort()

- L.unique()

- L.merge()

 

12. iterator

- 반복자, list에서만 사용 되는 것이 아니라 모든 STL container에서 사용된다.

- 포인터와 유사

- namespace std 사용

- 형식 : list<T>::iterator iter(list에서 사용한다고 가정)

- 형식2 : auto iter = L.begin()

- 예시 : iter = L.begiin() //헤드를 가르키는 중

- 예시2 : iter++, iter--, iter = L.end()