[STL] [1] 순차 컨테이너 정리 (Sequence Container, std::array, std::vector, std::list, std::deque)

STL과 Sequence Container

C++ Standard Template Library (표준 템플릿 라이브러리, STL)은 미리 구현된 임의 타입(Template) 자료구조와 알고리즘을 제공하는 라이브러리이다. 오랜 역사를 거쳐 최적화되었기에 성능과 정확성이 보장된다고 하는데, 따라서 C++ 개발 시 필수로 사용되는 라이브러리이다. (개인이 직접 작성한 알고리즘과 자료구조보다 거의 무조건 더 낫다고 생각하고 꼭 쓰자) STL은 알고리즘, 컨테이너, 함수자, 반복자라는 크게 4가지 구성 요소를 제공한다[1]. 

 

STL 컨테이너는 데이터를 저장하는 객체(정확히는 class template)를 의미한다. 좀더 쉽게 표현하면 STL 컨테이너는 데이터를 효과적으로 저장하기 위한 다양한 자료구조 구현체를 제공한다. 특히 어떠한 데이터 타입도 지원할 수 있도록 template으로 제공된다. 그 중 오늘은 Sequence Container에 대해서 정리하고자 한다.

 

Sequence Container는 이름 그대로, 데이터를 선형 자료구조로 저장하는 컨테이너이다. Sequence Container의 공통된 특징은 하나의 container에 포함된 데이터들은 sequentially 접근이 가능하다는 것이다[2]. (쉽게 말하면 하나, 둘, 셋 .. 등 데이터를 순서대로 접근할 수 있다는 것) 데이터를 저장하기 위해 사용되는 객체이기에 기본적으로 데이터 저장, 읽기, 제거 기능이 필요하다. 추가로 순서가 있다는 특성이 있기에 특정 순서에 데이터 저장, 읽기, 제거 기능이 필요하다.

 

대표적인 Sequence Container에는 array, vector, list, deque가 있다 (모두 std namespace에 정의됨). std::array, std::vector, std::list 등의 Sequence Container들은 모두 데이터를 순서대로 저장한다는 점에서 공통점이 있지만, 사실 내부적으로 모두 다른 자료구조로 구현되었다. 그렇기에 상황에 따라서 성능상에 큰 차이가 존재한다. 따라서 이러한 차이를 알고 어떤 상황에 어떤 Sequence Container를 사용할 지를 고를 수 있는 능력이 개발자에게는 중요할 것이다.

 

[2]에 따라 대표적인 4가지 구현체의 특징을 한줄로 정리하면 다음과 같다.

 

• std::array: 사이즈가 변하지 않는 배열로 그 사이즈는 컴파일 시 고정되어야 함 (static array)
• std::vector: 데이터 추가 시 자동으로 사이즈가 커지는 배열 (dynamic array)
• std::list: 이중 연결 리스트 (doubly linked list) 구현체
• std::deque: 앞과 뒤에 데이터를 추가할 수 있는 queue (double-ended queue)

 

앞서 말했듯, Sequence Container는 데이터를 선형으로 순서있게 저장한 자료구조이기에 특정 위치에 데이터 쓰기, 읽기, 제거 기능이 필수이다. (순서가 있기에, 순서와 관련된 요구가 존재함)

 

 

 

Array (std::array)

std::array[3]는 고정된 크기의 배열을 표현한 C++ STL 컨테이너이다. std::array는 compile time에 크기가 고정되는 경우에만 사용가능하며, 런타임에는 고정된 크기의 배열로 사용된다.

 

기존 C/C++ array와 마찬가지로 하나의 연속된 메모리 영역에 저장된다. 데이터 접근 시에는 operator[]를 통해 std::array내에 저장된 데이터에 접근할 수 있다. 이때 데이터 접근(읽기, 쓰기)은 O(1) (constant time) time complexity를 가진다. 쉽게 표현하자면 기존 C/C++ array를 대신하여 사용할 수 있다.

 

std::array는 compile time에 크기까지 결정되기에 heap memory 영역이 아닌, (몇가지 경우를 제외하고는) stack memory 영역에 저장된다[4]. 그렇기에 동적 메모리 할당 및 해제에 의한 overhead가 존재하지 않는다. 또한 memory fragmentation (메모리 단편화)가 발생하지 않는다. 이러한 부분에서 동적 할당이 필요한 다른 배열(ex, vector, int* A = new int[10])에 비해 성능상 이점이 존재한다.

 

 

 

Vector (std::vector)

std::vector[5]는 런타임에도 크기가 변할 수 있는 동적(dynamic) 배열을 나타내는 C++ STL 컨테이너이다. std::vector의 데이터 저장소 크기는 저장되는 데이터의 개수에 따라 런타임 시 동적으로 결정된다. 

 

기존 C/C++ 배열과 같이 연속된 메모리 영역에 저장되며, 따라서 주소 offset 연산을 통해서 std::vector내 데이터에 접근할 수 있다. std::array와 마찬가지로 operator[]을 통해 내부에 저장된 데이터에 접근할 수 있다. 쉽게 생각하자면 기존 C/C++ array, std::array를 대신하여 std::vector를 사용할 수 있다.

 

기존 C/C++배열, std::array과의 차이점은 동적으로 배열의 크기가 조절될 수 있다는 것이다. 이러한 점에서 std::vector는 얼마만큼의 데이터가 저장될 지 모르는 상황에서 매우 유용하게 사용될 수 있다. 이 기능은 내부적으로 자동 동적 할당을 통해 구현된다. 

 

예를 들면 다음과 같이 작동한다. 처음에 10개의 데이터를 저장할 공간을 동적 할당한다. 10개 초과의 데이터가 저장된다면, 잠시 데이터 저장을 멈추고 새롭게 20개의 데이터를 저장할 공간을 동적 할당한다. 그리고 기존 저장된 10개의 데이터를 크기 20의 공간에 복사한 후, 그 뒤에 11번째 데이터를 추가한다. 기존 사용되던 크기 10의 메모리 영역은 할당 해제한다. 이렇게 데이터가 추가될때마다[6] 어느정도 규칙을 가지고 메모리 공간을 증가시킨다. 특히 연속된 메모리 영역을 가질 수 있도록 매번 새롭게 기존보다 증가된 크기의 메모리 공간을 할당하고 기존의 영역에 포함된 데이터를 복사해놓는다.

 

 

 

List (std::list)

std::list[7]는 기존 자료구조 시간에 배운 Linked list를 구현한 STL이다. 단 Doubly-linked list로 구현되었기에, 양방향 (0번째에서 N-1번째로, N-1번째에서 0번째로) 탐색이 가능하다. Linked list 특성상 각각의 데이터는 물리적으로 구분된 메모리 주소에 저장될 수 있지만, 각각의 데이터는 인접한 (s번째 데이터는 s-1, s+1번째 데이터) 데이터의 주소정보(link)를 가지고 있기에 인접한 데이터에 접근할 수 있다.

 

std::list의 장점은 sequence의 어떠한 위치에라도 데이터를 추가하거나 제거하는 연산이 O(1) (constant time) time complexity를 가진다는 것이다. 앞서 설명한 std::vector의 경우 데이터들이 연속된 주소에 저장된다. 따라서 만약 중간에 위치한 데이터를 지울 경우, 순서 상 그 뒤에 위치한 데이터들 모두를 앞으로 옮겨야 한다. 그에 비해 std::list의 경우 연속된 주소에 존재하지 않고, 이웃한 데이터간의 link에 의해 유지되기에 link만 조작하면 쉽게 데이터를 추가, 삭제할 수 있다.

 

다만 탐색 시에는, operator[] (or at 연산)으로 임의 위치 데이터에 직접 접근이 불가능하다. 이 또한 마찬가지로 데이터가 연속적으로 위치하지 않기에 주소 offset 연산으로 데이터에 접근할 수 없기 때문이다. 무조건 link(n번째 데이터에 접근하기 위해서는 n-1번째 데이터에 저장된 n번째 데이터 주소를 알아야한다)를 이용해야 하기에, n번째 데이터에 접근하기 위해서는 첫번째 (or 마지막) 데이터부터 차례차례 탐색해나가야 한다.

 

추가 단점으로, linking 정보를 유지하지 위한 추가 메모리를 사용한다.

 

 

 

Deque (std::deque)

std::deque[8]는 "deck", "덱", "데크"라고 발음할 수 있는데, double-ended queue를 의미한다. Doule-ended queue는 양방향으로 데이터를 추가, 제거할 수 있는 queue를 의미한다. std::vector와 마찬가지로 container의 크기가 동적으로 커질 수 있다. 데이터들이 완벽히 연속적인 위치에 저장되지는 않지만(구체적인 구현은 큰 파트, 파트가 연결되어 저장된다), operator[]와 같은 임의 위치 데이터 접근이 허용된다. (다만 offset 연산을 통한 접근은 지원되지 않음 - undefined behavoir)

 

일반적으로 std::vector와 비슷한 기능들을 제공한다. (임의 위치 데이터 접근, 추가, 제거 등등) 다만 가장 첫번째에 데이터를 추가, 제거하는 경우에 효과적으로 사용될 수 있다. std::vector의 경우 0번째에 데이터를 추가하기 위해서는 기존 n번째 데이터를 모두 n+1번째로 옮기고, 비워진 0번째에 데이터를 추가한다. 그에 비해 std::deque는 0번째 앞에 데이터를 추가함으로서 쉽게 0번째에 데이터를 추가할 수 있다.

 

앞서 말했듯, std::deque는 연속적인 주소에 데이터들이 저장되지 않고, 데이터들은 큰 chunk, chunk 단위로 저장되고 chunk 단위에서만 데이터들이 연속적으로 존재한다. std::deque는 추가적으로 각 chunk들의 주소 정보를 가지고 있기에 데이터들이 하나의 array에 저장된 것처럼 사용할 수 있다. 이러한 구조는 약간은 복잡하고 operator[]연산에 조금 더 많은 시간이 걸리게 되지만, 이러한 구현을 통해 std::deque의 첫 번째에 데이터를 쉽게 저장할 수 있게 된다. (reallocation 없이)

 

 

 

Reference

[1] https://ko.wikipedia.org/wiki/표준_템플릿_라이브러리

[2] https://en.wikipedia.org/wiki/Sequence_container_(C%2B%2B) 

[3] std::array - cppreference.com

[4] std::vector versus std::array in C++ - Stack Overflow

[5] cplusplus.com/reference/vector/vector/

[6] https://stackoverflow.com/questions/26877654/do-c-vectors-shrink-after-elements-are-removed

[7] cplusplus.com/reference/list/list/

[8] cplusplus.com/reference/deque/deque/