[C++] 컨테이너(자료구조) 사용법 간단요약

vector, deque, set, map, stack, queue, priority_queue 등의 컨테이너와 자료구조에서 자주 사용하는 함수들을 간단하게 요약하였다.

 

먼저, 간단하게 표현하기 위해서...

편의상 템플릿 타입과 컨테이너 사이즈 타입(size_t)은 int 형으로 하였다.

템플릿 타입 명시 <int>를 생략하였다.

const를 생략했고 각 컨테이너의 iterator는 간단하게 iterator로만 표현했다.

 

진짜 진짜 주요한 함수만 확인해보려면 스크롤을 맨 아래로 내리자!

 

참조: https://en.cppreference.com/w/cpp/container

---

vector

Sequence Container로 요소에 대해 순차적으로 접근 할 수 있다. 

(forward, backward 둘 다 순회 가능)

생성자	vector(): 비어있는 벡터 생성 vector(int count): count 값 길이의 벡터 생성 (기본 값으로 채워짐) vector(vector& other): other 벡터를 복사하여 생성 vector(iterator begin, iterator end): begin 부터 end까지의 값으로 새로운 벡터 생성(복사)
요소 접근	int operator[]: index로 접근 (No bounds checking  -> runtime error) int at(int pos): index로 접근 (Bound checking, exception 발생) int front(): 첫번째 요소접근 (= [0]) int back(): 마지막 요소접근 (=[size-1] int* data: 데이터의 시작 위치 포인터 반환 (배열 처럼 사용가능)
반복자	iterator begin(): 첫번째 요소iterator iterator end(): 벡터의 마지막 iterator (주의: 마지막 요소가 아님)
크기	int size(): 현재 벡터의 사이즈 bool empty(): 벡터가 비어있는지 여부
컨트롤	void clear(): 모든 요소삭제 void push_back(int value): 벡터의 마지막 요소뒤에 새로운 요소추가 void pop_back(): 벡터의 마지막 요소삭제 iterator insert(iterator pos, int value): 해당 반복자에 값 넣기 iterator erase(iterator begin, iterator end): begin부터 end 전까지의 요소삭제

시간복잡도

operator[], at, front, back, begin, end, size, empty, push_back, pop_back : O(1)

clear, erase: O(N)

---

deque

 

배열 앞과 뒤를 모두 컨트롤 할 수 있는 자료구조로, 순서가 있는 Sequence Container 이다.

vector의 차이점은 배열의 앞에 요소를 추가하거나 첫 번째 요소를 제거할 수 있다는 점이다.

(forward, backward 둘 다 순회 가능)

생성자	deque(): 비어있는 deque 생성 deque(int count): count 값 길이의 deque 생성 (기본 값으로 채워짐) deque(deque& other): other를 복사하여 새로운 deque 생성
요소접근	int operator[]: index로 접근 (No bounds checking -> runtime error) int at(int pos): index로 접근 (Bound checking, exception 발생) int front(): 첫번째 요소접근 (= [0]) int back(): 마지막 요소 접근 (=[size-1]
반복자	iterator begin(): 첫번째 요소의 iterator iterator end(): 벡터의 마지막 iterator (주의: 마지막 요소가 아님)
크기	int size(): 현재 deque의 사이즈 bool empty(): deque이 비어있는지 여부
컨트롤	void clear(): 모든 요소삭제 void push_back(int value): dqque의 마지막 요소뒤에 새로운 요소 추가 void pop_back(): deque의 마지막 요소삭제 void push_front(): deque의 첫번째 요소앞에 요소 추가 void pop_front(): deque의 첫번째 요소 삭제 iterator insert(iterator pos, int value): 해당 반복자에 값 넣기 iterator erase(iterator begin, iterator end): begin부터 end 전까지의 요소삭제

시간복잡도

operator[], at, front, back, size, push_back, push_front, pop_back, pop_front: O(1)

 

Note: pop_front를 하면 index가 하나씩 떙겨지는 거에 주의하자.

---

set

 

Associative Container로, 데이터를 정렬하여 가지고 있고 특정 방법을 통해 데이터를 검색하여 접근한다.

(즉, index를 통해 순차적으로 접근 할 수 없다.)

또한 set은 Key의 개념으로 요소를 가지고 있기 때문에, 중복이 허용되지 않는다.

생성자	set(): 비어있는 set생성 set(set& other): other를 복사하여 set생성 set(Compare& comp): 정렬 시 사용할 함수 지정하여 set 생성
요소 검색	iterator find(int key): key 값을 찾고 iterator를 반환 (없으면 end() 반환) bool contains(int key): key값을 포함하고 있는지 여부 [C++20] iterator lower_bound(): key 값을 넘지 않는 첫번째 요소의 반복자 반환 (없으면 end() 반환) iterator upper_bound(): key 값을 초과하는 첫번째 요소의 반복자 반환 (없으면 end() 반환)
반복자	iterator begin(): 첫 번째 요소에 대한 iterator 반환 iterator end(): map의 마지막 iterator 반환 (주의: 마지막 요소가 아님)
크기	int size(): 요소의 개수 반환 bool empty(): set이 비어있는지 여부
컨트롤	void clear(): 모든 요소삭제 pair<iterator, bool> insert(pair<int, int>): map에 요소 삽입(key, value); 반환 값: pair<key에 대한 iterator, insert 성공 여부> (이미 key 값이 존재하면  insert되지 않고 false 반환)

시간 복잡도 (기본 Compare)

요소 검색: O(log N)

clear(): O(N)

---

map

 

Associative Container로, 데이터를 정렬하여 가지고 있고 특정 방법을 통해 데이터를 검색하여 접근한다.

(Key에 대해 순차적 접근을 할 수 없지만, key로 value를 참조할 수 있다.)

map의 iterator는 Key, Value의 쌍(pair)로 이루어져 있으며, Key 값에 대해 중복이 허용되지 않는다.

생성자	map(): 비어있는 map생성 map(map& other): other를 복사하여 map생성 map(Compare& comp): 정렬 시 사용할 함수 지정하여 map 생성
Value 접근	int operator[]: key값에 대한 value 값 반환 (없으면 새로 값을 만들고 default 값 반환) int at(int key): key값에 대한 value 값 반환 (없으면 exception 발생)
요소 검색	iterator find(int key): key 값을 찾고 iterator를 반환 (없으면 end() 반환) int count(int key): key 값에 대한 value값의 개수 반환 (있으면 1, 없으면 0) bool contains(int key): key값을 포함하고 있는지 여부 [C++20] iterator lower_bound(): key 값을 넘지 않는 첫번째 요소의 반복자 반환 (없으면 end() 반환) iterator upper_bound(): key 값을 초과하는 첫번째 요소의 반복자 반환 (없으면 end() 반환)
반복자	iterator begin(): 첫 번째 요소(pair<key, value>에 대한 iterator 반환 iterator end(): set의 마지막 iterator 반환 (주의: 마지막 요소가 아님)
크기	int size(): 요소의 개수 반환 bool empty(): set이 비어있는지 여부
컨트롤	void clear(): 모든 요소 삭제 pair<iterator, bool> insert(pair<int, int>): map에 요소 삽입(key, value); 반환 값: pair<key에 대한 iterator, insert 성공 여부> (이미 key 값이 존재하면  insert되지 않고 false 반환)

시간 복잡도 (기본 Compare)

요소검색, insert: O(log N)

clear(): O(N)

---

multiset

set과 동일하지만 같은 값을 가질 수 있다.

 

메서드 및 시간복잡도는 set과 동일하다.

---

multimap

map과 동일하지만 중복되는 key 값을 가질 수 있다.

key와 value 값이 1:1이 아니므로 operator[]와 at으로 접근할 수 없다.

 

요소 검색

iterator find(int key): key값에 대한 iterator 반환 (없으면 end() 반환) 만약 value 값이 여러개 있을 경우 그 중 하나 반환 (Finds an element with key equivalent to key. If there are several elements with key in the container, any of them may be returned.) int count(int key): key 값에 대한 value값의 개수 반환

 

시간복잡도

map과 동일하다.

---

unordered_set

Associative Container로, set과 달리 요소들을 정렬하여 가지고 있지 않는다.

정렬대신 내부적으로 버킷으로 구성된다. 이 버킷은 요소의 해시 값에 따라 달라지며 각 요소에 빠르게 접근 할 수 있게 해준다.

단, 이 컨테이너가 수정되면 해시가 변경되면서 컨테이너에 문제가 발생할 수 있으므로 요소 수정이 불가 하다.

 

시간 복잡도

요소 검색: O(1) (worst: O(N))

---

unordered_map

Associative Container로, map과 달리 요소들을 정렬하여 가지고 있지 않는다.

대신에 내부적으로 버킷으로 구성되는데, 이 버킷은 컨테이너의 key 값에 따라 달라진다. 같은 key 값이라면 같은 버킷을 가리킨다. 이 방법으로 각 요소에 빠르게 접근 할 수 있다.

정렬하지 않기 때문에 일반 map보다 훨씬 빠르다.

 

주요 메서드는 map이랑 동일하다.

 

시간 복잡도

요소 접근: O(1) (worst: O(N))

요소 검색: O(1) (worst: O(N))

 

---

stack

요소 접근이 top만 가능한 컨테이너로 FILO (First In Last Out)이다.

먼저 추가된 요소가 가장 나중에 나온다.

생성자	stack(): 비어있는 stack생성 stack(stack& other): other 스택을 복사한 새로운 stack 생성 stack(Container& cont): cont 형태의 컨테이너를 기반으로한 stack 생성
요소 접근	int top(): stack의 가장 위에 있는 값(최근에 추가된 값)을 반환
크기	int size(): 요소의 개수 반환 bool empty(): stack이 비어있는지 여부
컨트롤	void push(int value): 값 삽입 void pop(): 가장 위에 있는 요소 삭제

시간 복잡도 (기본 Container (vector))

insert, pop: O(1); [변동]

clear: O(N)

 

Note: stack에는 clear 함수가 없다. 따라서 반복문을 통해 요소를 제거해야한다.

Note2: C++은 다른 몇몇 언어와 달리 pop함수가 pop된 요소를 반환하지 않는다.

---

queue

 

기본적으로는 요소 접근이 front만 되는 컨테이너로 FIFO (First In First Out)이다.

먼저 추가된 요소가 먼저 나온다.

C++에서는 큐의 마지막 요소도 접근이 가능하다. (back)

생성자	queue(): 비어있는 queue생성 queue(queue& other): other 스택을 복사한 새로운 queue생성 queue(Container& cont): cont 형태의 컨테이너를 기반으로한 queue 생성
요소 접근	int front(): queue에서의 첫 번째 요소 반환 int back(): queue에서의 마지막 요소 반환
크기	int size(): 요소의 개수 반환 bool empty(): queue가 비어있는지 여부
컨트롤	void push(int value): 값 삽입 void pop(): queue에서의 첫 번째 요소 삭제

시간 복잡도

front, back, push, pop: O(1); [변동]

 

Note: queue에는 clear 함수가 없다. 따라서 반복문을 통해 요소를 제거해야한다.

Note2: C++은 다른 몇몇 언어와 달리 pop함수가 pop된 요소를 반환하지 않는다.

 

---

priority_queue

 

queue와 동일하지만 특정 조건(compare)로 정렬되어 있는 큐이다. 조건에 맞는 요소가 top이 된다.

compare 조건을 명시하지 않을 경우, 내림차순으로 정렬된다. (= 큰 값이 top 값이 된다.)

생성자	priority_queue(): 비어있는 queue생성 priority_queue(priority_queue& other): other 스택을 복사한 새로운 queue생성 prioirty_queue<type, container, compare>(): container를 이용하는 compare 조건의 우선순위 큐 생성
요소 접근	int top(): 정렬된 우선순위 큐에서의 첫 번째 요소 반환
크기	int size(): 요소의 개수 반환 bool empty():  우선 순위 큐가 비어있는지 여부
컨트롤	void push(int value): 값 삽입 (삽입 정렬) void pop(): 정렬된 우선순위 큐에서의 첫 번째 요소 삭제

 

시간 복잡도 (기본 container 및 기본 compare)

push: O(log N) [변동]

top: O(1)

---

몇몇 주의 컨테이너들의 주요 함수만 몇 가지 살펴보았다.

 

 

마지막으로 몇가지 혼동이 올 수 있는 함수만 빼서 정리하자면

	vector	set	map	priority_queue	stack	queue
요소 삽입	push_back	insert	insert(pair<key, value>)	push
요소 제거	-	erase		-	-	-
요소 접근	[], at	-	[], at (value 접근)	top		front, back
가장 가까운 요소 제거	pop_back	-	-	pop
크기 가져오기	size

 

다음 사이트에 위에서 나타난 내용들이 매우 자세히 설명이 되어 있다.

https://en.cppreference.com/w/cpp/container

Containers library - cppreference.com

 

 

시간 복잡도에 대해서...

포스팅에서는 사용되는 container에 대해서 기본값일 때의 시간 복잡도를 작성해 놓았지만, 결국에 이 시간 복잡도는 달라질 수 있음을 기억하자.

 

---

수정 로그

2023.08.08 - 정리 표에서 stack과 queue가 서로 반대로 나와있었던 점 수정