STL Container - 개요

C++를 주로 사용하는 개발자라면 빼놓을 수 없는 것이 바로 STL의 Container입니다.

자료구조를 배워본 사람이라면 각 컨테이너마다 어떤 특징이 있고, 무엇을 기반으로 해당 컨테이너가 개발되었는지 대략적으로 파악할 수 있을 것입니다.

본문에서는 컨테이너에 대한 기본적인 개요와 종류를 알아보고, 향후 각 컨테이너에 대한 자세한 설명과 특징, 장단점 등을 정리해 보겠습니다.

 

컨테이너?

컨테이너는 STL 알고리즘과 결합하여 다양한 데이터 구조를 표현할 수 있도록 설계된 자료형입니다.

각 컨테이너는 자신만의 특징을 가지고, 개발자는 자신이 구현하고자 하는 목적에 맞는 컨테이너를 채택하여 프로그램의 효율성을 높일 수 있습니다.

닭잡는데 소잡는 칼을 사용할 필요는 없습니다

 

효율성?

효율성을 수치화할 수 있는 가장 대표적인 수단입니다. Big-O 표기법에 의거하여 우리는 해당 컨테이너가 얼마의 성능을 가질 수 있는지 나타낼 수 있습니다.

유형	표기법
Constant	O(1)
Linear	O(n)
Logarithmic	O(log(n))
n-log-n	O(n ∗ log(n))
Quadratic	O(n²)

자세한 내용은 아래 포스트에 상세하게 설명되어 있습니다.

https://mystes.tistory.com/122

알고리즘에 대한 고찰 (시간 복잡도)

 

컨테이너의 종류

컨테이너는 대표적으로 4가지 유형을 갖습니다.

• Sequence
• Associative
• Adaptor
• Unordered

 

Sequence

모든 요소가 특정 위치를 갖는 정렬된 컨테이너입니다. 시퀀스 컨테이너는 순차적으로 엑세스 할 수 있는 데이터 구조가 특징입니다.

대표적인 시퀀스 컨테이너로는 vector가 있습니다.

• vector
• deque

 

Associative

연관 컨테이너는 탐색에 최적화된 정렬된 컨테이너입니다. 이것은 O(log N)의 효율성을 가지며 대표적인 연관 컨테이너로는 map이 있습니다.

Associative Container 더 알아보기

 

Unordered associative containers

C++11 이후부터 추가된 연관 컨테이너의 확장 버전으로, 대표적인 타입으로는 unordered map이 있습니다.

이것은 비정렬을 통하여 더욱 빠른 탐색 속도를 보여주지만 삽입 및 삭제의 순서가 보장되지 않습니다.

예를들어 부분 압축 파일을 unordered map에 저장하여 호출할 경우, 압축 파일의 순서가 보장되지 않기 때문에 기대하지 않은 동작이 호출될 수 있습니다.

반면 독립적인 압축 파일을 여러 개 다룬다고 가정할 때, 각 압축 파일은 상호 종속성이 없기 때문에 map보다 효율적인 데이터 구조를 가질 수 있습니다.

Unordered associative containers 더 알아보기

 

Container adaptors

컨테이너 어뎁터의 경우 직접적으로 사용할 수 있지만, 주로 위 3개의 컨테이너를 구현하기 위한 베이스 템플릿으로 사용되는 구조입니다.

알고리즘에 자주 등장하는 queue 또는 stack이 이것에 해당됩니다.

또는 C++23 버전에서 컨테이너 어뎁터 종류 중 4종의 flat 자료형이 추가되었습니다.

flat에 대한 자세한 내용은 여기를 참고하세요.