C++ 자료구조 종류 및 개요

선형 자료구조(Linear Data Structure)

종류	형식	특성	시간 복잡도	메소드
Vector	vector<int> v	동적 할당, 정적 할당 - 연속된 메모리 공간에 위치한 같은 타입의 요소들 모음 - 숫자인덱스 기반 랜덤 접근 가능 - 중복 허용	맨 뒤 삭제,삽입 O(1) 맨 뒤나 앞이 아닌 요소를 삭제 삽입 O(n)	push_back() pop_back() erase() find() clear() fill()
					Array	int a[10];	정적 할당 - 연속된 메모리 공간에 위치한 같은 타입의 요소들 모음 - 숫자인덱스 기반 랜덤 접근 가능 - 중복 허용		X
List	list<int> a;	데이터를 감싼 노드를 포인터로 연결해서 공간적 효율성을 극대화 - 요소가 인접한 메모리 위치에 저장되지 않는 선형 자료 구조 - 순차적 접근만 가능 - next, prev라는 포인터로 연결됨 - 중복 허용 *종류: 싱글연결리스트, 이중연결리스트, 원형연결리스트 등		push_back() push_front() insert() erase() pop_back() pop_front() front() back() clear()
Map (Dictionary)	map<string,int> mp; unordered_map<string, int> umap;	고유한 키를 기반으로 key-value쌍으로 이루어져 있는 정렬된 연관 컨테이너 *해당 인덱스에 참조만 해도 맵의 요소가 생긴다 *unordered_map 정렬되지 않음	Map 삽입,삭제,수정,탐색 O(logN) Undordered Map 평균적으로 O(1), 최악의 경우 O(N)	insert() size() erase() find() clear()
Set	set<pair<string, int>> st; multiset<int> s;	고유한 요소만을 저장하는 컨테이너 - 중복된 값을 제거하며 map과 같이 자동 정렬 *중복되는 요소도 집어넣을 수 있는 자료구조
Stack	stack<string> stk;	- LIFO, Last In First Out ex. 재귀함수, 웹브라우저 방문기록 ex. 문자열 폭발, 아름다운 괄호만들기, 짝찾기 키워드, "교차하지 않고"	삽입 삭제 O(1) 탐색 O(n) *n번째 요소를 찾는다할 때 n번 반복해야 함	push() pop() top() size()
Queue	queue<int> q; deque<int> dq;	- FIFO, First In First Out *deque: 앞 뒤로 삽입,삭제 참조 가능	삽입, 삭제 O(1) 탐색 O(n)	push() pop() front() size()
Priority Queue	priority_queue<int, vector<int>,greater<int>> pq;	각 요소에 어떠한 우선순위가 추가로 부여되어있는 컨테이너 세번째 파라미터에 정렬 기준. *greater<type>:오름차순 1-2-3 *less<type>: 내림차순 3-2-1		push() pop() top() size()
Struct	struct Ralo{ int a,b; double c,d,e; };	언어 자체에서 제공하는 자료 구조가 아닌 개발자가 커스텀한 자료구조 커스텀하게 정렬 추가하거나, 다른 타입의 요소들 모을 수 있음.