STL 자료구조

무조건 vector, find() 사용하지 말고, 자료구조 적절하게 사용할 것
find( )는 생각보다 시간 효율이 좋지 않다.

vector의 find() : O(N)
set의 find() : O(NlogN)
unordered_set의 find() : O(1) //내부적으로 Hash로 구현되어 있음

🌟정리

1. Map
   데이터를 인덱스 번호가 아닌 key값으로 접근하고 싶을 때

2. Set
   그냥 넣으면 알아서 중복 제거 + 정렬된 상태로 저장

3. Priority Queue
   최솟값 & 최댓값 빠르게 찾고 싶을 때 => top( )하면 무조건 max값
   min값 찾고 싶으면 greater<int> 넣고, 담을 container 같이 선언해주면 됨

vector

• 크기가 가변적인 배열
• 배열처럼 인덱스로 접근 가능
• 인덱스로 접근하기 때문에 검색 측면에서 시간복잡도가 좋음
  But. 원소 삽입&삭제 할 경우, 전부 한 칸씩 밀어내야 하므로 시간복잡도가 o(n)으로 구림

#include <vector>

front() : 첫 번째 원소
back() : 마지막 원소
begin() : 첫번째 위치 (포인터) -------------------- sort 라이브러리 쓸 때 유용
end() : 마지막의 다음 위치 (포인터) -------------- sort 라이브러리 쓸 때 유용
push_back(k) : 마지막에 데이터 추가
pop_back() : 마지막에서 데이터 뽑기
size() : 원소의 개수
clear() : 비우기
erase(iter) : 특정 원소 삭제

vector<int> v1;
vector<int> v2 = {1, 2, 3, 4, 5};
vector<int> v3(n,1); //크기 n, 전부 1로 초기화 된 배열

v2.push_back(6); // [1, 2, 3, 4, 5, 6]
v2.erase(v2.begin() + index);

list

• 비연속적인 메모리
• 인덱스로 접근 불가능하고, iterator를 통해 순회해야 함
• list는 노드를 연결만 하기 때문에 원소 삽입&삭제 시에 시간복잡도 우위를 가짐

#include <list>

list<char> l(str.begin(), str.end());
auto cursor = l.end();

for (auto iter = l.begin(); iter != l.end(); iter++) {
	cout << *iter;
 }

stack

• LIFO
• 재귀함수, DFS, 역순 문자열에서 사용

#include <stack>

push(k) : top에 데이터 추가
pop() : top에서 데이터 뽑기
top() : top에 있는 원소
size() : stack의 크기
empty() : stack이 비어있는지 확인

stack<int> s;
	
s.push(7);
s.push(5);
s.pop();
	
while(!s.empty()) {
	cout << s.top() << ' ';
	s.pop();
}

queue

• FIFO
• BFS에서 사용

#include <queue>

push(k) : 마지막에 데이터 추가
pop() : 맨앞에서 데이터 뽑기
front() : 첫 번째 원소
back() : 마지막 원소
size() : queue의 크기
empty() : queue가 비어있는지 확인

queue<int> q;

q.push(7);
q.push(5);
q.pop();

while(!q.empty()) {
	cout << q.front() << ' ';
	q.pop();
}

deque

덱 (double ended queue)

• vector와 다르게 양쪽에서 삽입/삭제 가능
• 스택 + 큐를 합친 자료구조

#include <deque>

push_front(k) : 마지막에 데이터 추가
pop_front() : 마지막에서 데이터 뽑기
push_back(k) : 마지막에 데이터 추가
pop_back() : 마지막에서 데이터 뽑기

나머지는 멤버 변수는 vector와 거의 동일

deque<int> dq;

dq.push_front(2);
dq.push_back(5);
dq.pop_back();
dq.pop_front();

priority queue

• 최댓값/최솟값 빠르게 찾기 위해 사용 => 반정렬 상태라 시간복잡도 good👍🏻
• heap으로 구현 => 트리 구조라 index 탐색 아예 불가능
• 기본은 최대 힙 (top이 젤 큰 수)
  ⭐최소 힙 구현하고 싶으면 비교연산자에 greater<int> 넣고, 담을 container 같이 선언해줘야 함
  

#include <queue>

두 가지 선언 방식
1. priority_queue<자료형> 변수명;
선언한 자료형 변수들을 내림차순으로 정렬하는 우선순위 큐 선언
2. priority_queue<자료형, Container, 비교함수> 변수명;
선언한 자료형 변수들을 비교 함수에 따라 정렬하는 우선순위 큐 선언

push(k) : top에 데이터 추가
pop() : top에서 데이터 뽑기
top() : top에 있는 원소
size() : priority queue의 크기
empty() : priority queue가 비어있는지 확인

priority_queue<int> pq1;
priority_queue< int, vector<int>, greater<int>> pq2;

pq.push(5);

set

• Associative 컨테이너 cf) 배열 같은 Sequence 컨테이너

• key라 불리는 원소들의 집합으로 이루어짐

• 균형 이진 트리로 구현

• key값 중복 X

• insert를 통해 입력하면 자동 오름차순 정렬

• ⭐중복 피하며 정렬까지 하고 싶을 때

#include <set>

insert(k) : 원소 k 삽입
begin() : 맨 첫번째 원소를 가리키는 iterator를 반환
end() : 맨 마지막 원소를 가리키는 iterator를 반환
find(k) : 원소 k를 가리키는 iterator를 반환
size() : set의 원소 수
empty() : 비어있는지 확인

set<int> s;

s.insert(10);


set<int>::iterator iter;

for (iter = s.begin(); it != s.end(); ++iter) {
	출력문
}


iter = s.find(30); // 값 존재 여부 확인

if ( iter != s.end() ) {
	존재
}
else {
	존재하지 않음
}

• Set은 자료를 정렬해서 저장함 => 정렬 필요없이 빠른 검색 원할 때 unordered_set 사용!!

#include <unordered_set>

unordered_set<string> s;

map

• map은 인덱스로 접근하는 것이 아니라 key값으로 접근하는 것

• Associative 컨테이너 cf) 배열 같은 Sequence 컨테이너

• <key, value>의 쌍으로 저장 cf) set은 원소로 key만 저장

• key값 중복 X

• insert를 통해 입력하면 자동 오름차순 정렬

• key로 값 찾을 수 있음

#include <map>

insert(make_pair(k, v)) : 원소를 key와 value의 pair로 삽입
erase(k): key값 k를 갖는 원소를 삭제
begin() : 맨 첫번째 원소를 가리키는 iterator를 반환
end() : 맨 마지막 원소를 가리키는 iterator를 반환
find(k) : key값 k에 해당하는 iterator를 반환
size() : map의 원소 수
empty() : 비어있는지 확인

map<char, int> m;

/* 데이터 삽입하는 세 가지 방법 */
m.insert(pair<char, int>('a', 10));
m.insert({'b', 20});
m['c'] = 30;

cout << m['a']; // 10 출력

• Map은 자료를 정렬해서 저장함 => 정렬 필요없이 빠른 검색 원할 때 unordered_map 사용!!

#include <unordered_map>

unordered_map<int, string> m;

* pair

• 두 가지 자료형을 하나의 쌍으로 묶음
  (first, second)

#include <algorithm>
#include <vector>

pair<int, char> p1;

p1.first = 1;
p1.second = a;

p = make_pair(1, a)

* tuple

• 세 가지 이상의 자료형을 하나의 쌍으로 묶음

#include <tuple>

tuple<string, string, string> t;

t =make_tuple(name, time, inout); //MINSU 15:40 IN
get<0>(t); //name
get<1>(t); //time
get<2>(t); //inout