Machineboy空
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; }; |
언어 자체에서 제공하는 자료 구조가 아닌 개발자가 커스텀한 자료구조 커스텀하게 정렬 추가하거나, 다른 타입의 요소들 모을 수 있음. |