C++ STL 컨테이너 정리

 

1. 시퀀스 컨테이너 (요소의 순서가 유지됨)

vector

ㄴ 연속적인 메모리 공간에 요소들을 저장한다. (배열 기반 컨테이너)

ㄴ 중간에 원소를 삽입(insert)거나 지우는(erase) 연산은 O(n)이기 때문에 비효율적이다.

 

1. push_back() 

ㄴ 맨 뒤에 원소를 추가

ㄴ O(1)의 시간 복잡도

ㄴ 공간을 초과할 경우 새로운 공간을 할당하기 위해 O(n) 소요

 

2. size()

ㄴ 벡터가 가진 원소의 개수를 리턴한다.

 

3. at(), []

ㄴ 벡터의 원소에 접근한다.

 

4. resize()

ㄴ 원소의 개수를 조정한다.

ㄴ capacity보다 작은 값을 인자로 주면 원소의 개수를 줄인다.

ㄴ capacity보다 큰 값을 인자로 주면 capacity를 인자 값으로 늘리고, 빈 공간은 원소의 기본값(기본 생성자 호출)으로 채운다.

 

5. reserve()

ㄴ capacity를 재설정한다.

ㄴ 기존 capacity 보다 작은 값을 인자로 받을 경우엔 아무일도 일어나지 않는다.

 

6. pop_back()

ㄴ 마지막 원소를 제거

ㄴ O(1)의 시간 복잡도

 

list

노드 기반의 컨테이너 (double linked list)

중간에 데이터 삽입이나 삭제 연산이 O(1)의 시간 복잡도를 가지기 때문에 중간에 데이터 삽입이나 삭제가 자주 발생할 경우 사용하면 좋다.

원소에 바로 접근할 수 있는 수단이 없다.

 

deque

배열 기반 컨테이너

vector와 다른점

ㄴ 자료들이 여러개의 메모리 블록에 나뉘어 저장된다.

ㄴ push_front(), pop_front() 메서드를 사용하여 맨 뒤 뿐만 아니라 맨 앞에서 원소를 빠르게 O(1)로 넣고 지울 수 있다. 

ㄴ vector는 삽입으로 인해 메모리 용량을 초과할 경우에 기존의 메모리를 삭제하고 새로운 메모리를 할당해 원소들을 복사하는데, deque은 메모리 블럭을 새로 할당한다. (vector에 비해 확장하기 용이하다)

ㄴ 중간에 원소를 추가/제거 하는 경우에도 vector에 비해 효율이 좋다. 원소들을 앞과 뒤로 밀어낼 수 있기 때문이다.

 

2. 연관 컨테이너 (요소의 위치를 지정할 수 없음)

map

key-value 쌍으로 값을 저장한다 (연관 컨테이너)

균형 이진 트리를 이용한 빠른 검색에 특화된 자료구조이다.

검색 연산은 O(logn)의 시간 복잡도를 가진다.

중복된 key값을 허용하지 않는다.

삽입과 삭제가 일어날 때마다 원소 쌍들은 자동으로 정렬 된다. 삽입과 삭제는 O(logn) 시간 복잡도를 가진다.

iterator는 중위 순회를 통해 원소에 접근하게 해준다.

#include <iostream>
#include <map>
using namespace std;

int main(){
	map<int, string> temp;
    
    // map에 원소 쌍을 추가하는 법
    temp.insert({40, "photo"}); 
    temp.insert(make_pair(4, "world"));
    
    // key를 사용하여 value에 접근하는 법
    cout << temp[40] << endl;

    // 수정도 가능하다.
    temp[40] = "hello";
    
}

 

 

hashmap

해시 테이블을 이용하여 key-value 쌍을 저장하는 자료구조

컨테이너에 자료를 추가하거나 삭제하는데 다른 컨테이너보다 비용이 크기 때문에 빈번하게 자료의 삽입 삭제를 피해야 한다.

많은 자료를 저장하고, 검색 속도가 빨라야 하는 경우에만 사용하는 것이 좋다.

 

set

Map과 거의 비슷하지만 key-value가 아닌 value만 저장한다.

 

3. 컨테이너 어댑터 (기능이 변형된 컨테이너, 반복자를 지원하지 않음)

stack

LIFO (Last in First out) 방식으로 동작한다.

 

내부 컨테이너 구조를 선택할 수 있다. (vector, deque, list) 디폴트는 deque이다.

push(), top(), pop() 함수를 사용한다.

 

queue

FIFO (First in First out) 방식으로 동작한다.

내부 컨테이너 구조를 선택할 수 있다. (deque, list) 디폴트는 deque이다.

 

front(), back(), push(), pop() 함수를 사용한다.

 

priority_queue

우선순위 큐는 힙 자료구조(배열)을 채택하기 때문에 내부 컨테이너는 (vector, deque)로 구현되어 있다. 디폴트는 vector이다.

프로그래머가 정한 우선순위에 따라 우선순위가 가장 높은 데이터가 먼저 나온다.

삽입과 삭제가 O(logn) 시간복잡도를 가진다.

 

기본 우선순위는 최대힙(내림차순, 부모 노드가 자식 노드보다 작지 않음)이다. (가장 큰 수가 루트 노드에 있다. pop()을 사용하면 루트 노드를 제거하고 값을 얻는다.)

push(), top(), pop() 함수를 사용한다.

 

std::priority_queue<int> pq;

// 내부 컨테이너를 설정할 수 있다.
std::priority_queue<int, std::deque<int>> pq1;

// 내부 컨테이너 설정 + 오름차순 우선순위
std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;

 

참조:

https://blog.naver.com/yoochansong/221739086178