[C++] C++의 STL

C++로 알고리즘 문제를 풀다보면 자연스럽게 STL을 쓰게 되는데 이 STL이 어떻게 구성되어있는지 글을 정리해 보려 한다.

STL이란?

- STL은 Standard Template Library의 약자로, 여러 자료 구조, 함수, 알고리즘 등을 쓰기 쉽게 정형화하여 라이브러리화 해둔 것이다.

 

- STL은 모두 컨테이너로 정의되어 있고 크게 4개의 라이브러리로 나뉜다.

• 컨테이너 라이브러리(Container) : 자료구조를 사용할 수 있는 라이브러리로, 데이터를 저장하는 객체를 사용할 수 있다.
• 반복자 라이브러리(Iterator) : iterator라 불리는 반복자가 정의되어 있는 라이브러리로, 컨테이너의 데이터 위치를 가리키는 포인터처럼 동작하는 객체이다.
• 알고리즘 라이브러리(Algorithm) : 자주 사용하는 유용한 알고리즘이 담겨 있는 라이브러리로, sort, binary_search, find_element 등과 같은 정렬, 검색, 연산 등을 해결하는 함수가 있다.
• 함수자(Function Object) : STL을 함수 호출 연산자 operator()로 오버로드하는 클래스들을 포함한다.

컨테이너 라이브러리

- 컨테이너란, 객체를 일정한 방식으로 저장하고 조직화하는 객체이다. 컨테이너를 사용한다는 것은 데이터에 접근하기 위해 반복자를 사용한다는 것이다.

 

- 컨테이너의 종류는 3가지가 존재하는데, 각각 순차 컨테이너, 연관 컨테이너, 컨테이너 어뎁터이다.

• 순차 컨테이너(Sequence Container) : 객체를 선형적으로 저장하는 컨테이너이다. 멤버 함수를 호출하거나 반복자로 차례대로 객체들에 접근이 가능하다. vector, list, deque가 이에 포함된다.
• 연관 컨테이너(Associative Container) : 객체들을 연관된 키와 함께 저장하는 컨테이너이다. 키 또는 반복자를 통해 객체들에 접근이 가능하다. map, set과 같은 종류들이 이에 포함된다.
• 컨테이너 어댑터(Container Adapter) : 컨테이너 위에서 돌아가는 자료구조로, 보통 vector로 구현이 된다. stack, queue, priority_queue가 이에 포함된다.

순차 컨테이너

Vector

• element가 index를 가지고 선형적으로 저장되어 있는 순차 컨테이너의 한 종류이다.
• vector 내의 원소에 index를 사용하여 접근하므로 O(1)의 시간이 소요된다.
• 원소를 중간에 삽입하거나 삭제하는데에는 원소를 1칸 씩 옮겨줘야하므로 O(n)의 시간이 소요된다. 하지만 끝에 삽입하거나 삭제하는 경우에는 O(1)의 시간이 소요된다.
• 동적 배열로 구현되어 있어, 메모리를 새로 할당받아 크기를 늘리거나 해제하여 크기를 줄일 수 있다.
• list와 다르게 원소들이 메모리에 연속적으로 존재한다.

List

• doubly linked list로 구현되어 있는 순차 컨테이너의 한 종류이다.
• 따라서, 임의 위치의 접근하는 것이 불가능하다.
• 원소 삽입, 삭제가 어느 위치에서 이루어지든 O(1)의 시간이 소요된다.
• 원소들이 메모리 상에서 연속적으로 위치해있지 않는다.

Deque

• 벡터와 비슷하게 임의 위치 원소에 접근하는데 O(1)의 시간이 소요된다.
• 맨 앞/뒤 원소의 삽입, 삭제에 O(1)의 시간이 소요된다.
• 임의의 위치에 원소를 삽입하거나 삭제하는 것은 O(n)의 시간이 소요된다.
• 벡터와 다르게 원소들이 메모리에 연속적으로 저장되어 있지 않고, 여러 데이터를 저장할 수 있는 블록의 형태들로 흩뿌려 저장되어 있다.
• 원소들이 어디에 저장되어 있는지 정보 보관을 위해 추가적인 메모리가 더 필요하다.(블록의 위치 정보 저장)

연관 컨테이너

set

• Red Black Tree 자료구조로 구현되어 있다.(RB Tree란? : https://jeokyong-development.tistory.com/28)
• 중복된 원소가 들어가지 못한다.
• key가 bool 타입의 value와 연결되어 있어, key의 존재 유무만 확인해준다.
• 원소 삽입, 삭제, 탐색에 O(log N)의 시간이 소요된다.
• 반복자를 활용하여 순차적으로 set에 저장되어 있는 원소를 탐색할 수 있다.

map

• Red Black Tree 자료구조로 구현되어 있다.
• set과 달리, key와 value를 함께 저장할 수 있다.
• 중복된 key를 혀용하지 않는다.
• set과 같은 자료구조로 되어 있기 때문에 삽입, 삭제, 탐색에 O(log N)의 시간이 소요된다.
• map의 원소는 std::pair 타입으로 저장된다.
• 반복자를 통해 순차적으로 map에 저장되어 있는 원소를 탐색할 수 있다.

unordered_map / unordered_set

• Hash function을 이용하여 구현되어 있다.(map, set과 달리 원소가 정렬되어 있지 않다)
• 원소 삽입/삭제, 탐색이 모두 O(1)의 시간을 소요한다.
• Hash 중, 체이닝(chaining) 기법을 활용해서 구현되어 있기 때문에, 최악의 경우 탐색에서는 O(N)의 시간이 소요된다.

컨테이너 어댑터

stack

• LIFO(Last In First Out)를 따르는 자료구조
• 순차 컨테이너인 deque으로 구현되어 있다.
• 삽입과 삭제 모두 O(1)의 시간이 소요된다.
• stack의 top, 가장 위에 있는 값에만 접근이 가능하다.

queue

• FIFO(First In First Out)를 따르는 자료구조
• 순차 컨테이너인 deque으로 구현되어 있다.
• 삽입과 삭제 모두 O(1)의 시간이 소요된다.
• queue의 front, 맨 앞에 있는 값에만 접근이 가능하다.

priority_queue

• heap 자료구조로 구현되어 있는 컨테이너 어댑터의 한 종류이다.
• 기본적으로 큰 값이 가장 위에 올라가 있는 max_heap 구조이지만 greater을 사용하여 선언하면 min_heap으로 사용할 수 있다.

ex) priority_queue<int> -> max_heap, priority_queue<int, vector<int>, greater<int>> -> min_heap

• priority_queue의 top, 맨 위에 있는 값에만 접근이 가능하다.
• 삽입, 삭제에 O(log N), top에 있는 원소에 접근하는데에는 O(1)의 시간이 소요된다.

 

출처 : https://www.simplilearn.com/tutorials/cpp-tutorial/cpp-standard-template-library