[Basic C++] #31-2_STL 컨테이너, vector, list, deque, set, map

 

[Basic C++] #31-2_STL 컨테이너, vector, list, deque

 

C++ 개발에서 표준 라이브러리(STL)에 대해 알아보겠습니다.

"전문가를 위한 C"의 15 항목, "C++ 표준 라이브러리 살펴보기"에 해당하는 내용입니다.

 

---

 

Overview

 

1. vector
2. list
3. deque
4. set
5. map

 

#0. vector

1. 개념

• vector는 STL이 제공하는 순차 컨테이너에 대한 템플릿 클래스입니다.
• vector는 지정된 형식의 요소를 선형 배열에 저장하고, 모든 요소에 대한 빠른 임의의 접근이 가능합니다.
• vector의 성능은 컨테이너 끝에서 수행하는 삽입 및 제거 작업의 성능은 O(1) 상수 시간으로 비교적 빠릅니다. 하지만, 컨테이너 중간에서 수행하는 삽입 및 삭제 작업의 성능은 O(n) 선형 시간입니다.
• 배열과 달리 vector의 크기는 유동적입니다.  
• vector의 메모리 사이즈가 커지면, 메모리 재할당이 발생합니다.

 

2. 비교(deque, list)

• 컨테이너의 시작 지점과 끝 지점에서 수행하는 삽입 및 삭제 작업은 vector 보다 deque가 더 빠릅니다.
• 컨테이너의 모든 위치에서 삽입 및 삭제 작업은 list가 더 빠릅니다. 

 

#1. list

1. 개념

• list는 STL이 제공하는 순차 컨테이너에 대한 템플릿 클래스입니다.
• 특정 항목을 기준으로 앞의 항목과 뒤의 항목의 위치만 관리하며, 이중 연결 리스트의 구조를 갖고 있습니다.
• 순차 컨테이너 내 모든 위치에서 효율적인 삽입 및 삭제를 허용합니다.
• vector나 배열과 달리, 저장하고 있는 항목들이 메모리에 연속적으로 위치하지 않을 수도 있습니다.
• 만약, 이중 연결 리스트가 아니라 단방향 연결 리스트를 필요로 한다면, "forward_list"를 사용하면 됩니다.

 

#2. deque

1. 개념

• deque는 STL이 제공하는 지정된 형식의 요소들을 저장하는 양방향  큐(Double Ended Queue)입니다. 
• dequeue는 모든 요소에 대한 빠른 임의의 접근이 가능하며, 시작 위치와 끝나는 위치에서 수행하는 삽입 + 삭제 연산에 분할 상수 시간의 빠른 성능을 제공합니다.
• 단, 중간 항목들에서 수행하는 연산은 느리겠죠.

 

#3. set

1. 개념

• set은 STL이 제공하는 중복이 불가능한 균형 이진트리 자료구조를 갖는 가변 크기 연관 컨테이너입니다.
• set은 자동으로 정렬되는 고유한 key값을 원소로 이루어진 집합입니다.
• set에 저장되는 항목에 순서가 자동으로 부여됩니다. 왜냐하면, 저장되는 항목을 나열할 때 항목의 타입에 적용되는 "operator >" 연산자, 즉 사용자 정의 비교 연산자가 적용된 순서로 항목이 추출되기 때문입니다. 
• 균형 이진트리에 저장된 항목들은 중위 순회(왼쪽 하위 트리를 방문 후 뿌리를 방문)를 통해 출력됩니다.
• "set"은 항목들이 순서를 갖고 삽입, 삭제, 그리고 탐색 연산이 비슷한 비율로 수행되기를 원할 때 사용하기 좋습니다.
• 만약, 항목 간의 중복을 허용하고자 한다면, "multiset"을 이용할 수 있습니다.

 

#4. map

1. 개념

• map은 STL이 제공하는 중복이 불가능한 키와 데이터 값을 한 쌍으로 레드-블랙 이진트리 자료구조의 연관 컨테이너입니다.
• map의 각 요소는 키 값을 기준으로 지정된 비교 함수에 따라서 자동으로 정렬(오름차순 디폴트)되어 있습니다.
• map의 탐색, 삽입, 그리고 삭제 작업은 O(log n)의 시간 복잡도를 갖습니다.