UNSEEN 대비 4. C++ 주요 컨테이너 (1) (array, vector, list)

1. C++의 주요 컨테이너

C++에서 컨테이너란 임의 타입의 객체를 보관할 수 있는 자료형을 말한다.

개발자는 필요하다면 트리, 그래프, 연결리스트 등 원하는 스펙으로 자료구조를 구현해야 한다. 하지만 C++에서는 표준 템플릿 라이브러리(STL, Standard Template Library)에서 다양한 컨테이너를 제공하고 있기 때문에 보통 STL 컨테이너로 빠르게 원하는 기능을 구현할 수 있다.

C++의 표준 템플릿 라이브러리에는 array, vector, list, map, unordered_map 등의 컨테이너가 있다. 이번 글에서는 기본적인 컨테이너 중에 대해 개요와 동작 원리를 알아보자.

2. 배열(std::array)

정의

// 헤더파일 <array>의 선언
template<class T, [std::size_t](http://en.cppreference.com/w/cpp/types/size_t) N> 
struct array;

std::array는 고정된 크기의 배열을 담는 컨테이너이다.

이 컨테이너는 C 스타일 배열 T[N]과 비슷하게 동작한다. 다만 C 스타일 배열과 달리 배열의 이름이 포인터 T*로 자동 변환되지 않는다. C처럼 초기화 배열로 초기 값을 설정할 수 있다.

EX) std::array<int, 3> a = {1, 2, 3};

std::array는 기존 C언어 배열과 같은 형태를 유지하면서 C++에서 추가된 기능을 함께 사용할 수 있다. 자기 배열의 크기도 알고 대입 연산(assignment)도 지원하며 반복자를 통한 순회도 가능하다.

길이가 0일 때(N==0) array.begin() == array.end()가 되며 고유한 값으로 정의된다고 한다. 이때 front(), back()를 호출하면 결과가 정의되지 않는다.

std::array는 N개의 같은 원소를 담는 tuple을 표현할 때에도 사용할 수 있겠다.

반복자를 사용할 수 없는 순간

std::array는 객체가 살아있는 동안에는 반복자가 무조건 유효하다. 하지만 std::swap를 호출하고 나서는 반복자가 같은 위치를 가리키고 있기 때문에 가리키는 값이 달라질 수도 있다.

템플릿 형식인자

T - 배열의 원소 타입으로, 이동 생성자와 이동 대입 연산자를 사용할 수 있어야 한다.

N - 배열의 길이. 0이 될 수도 있다.

동작 원리

C 스타일 배열 구조

• 배열은 기본적으로 연속된 메모리 공간에 할당된 데이터를 가리킨다.
• 일정한 메모리 크기 단위로 할당하기 때문에 동일한 자료형만 담을 수 있다.
• 배열은 연속된 메모리 공간에서 첫 주소를 담는 포인터와 같다.
• C언어 배열(int arr[SIZE])은 배열의 이름(여기서는 arr)이 배열의 주소를 가리킨다. 다만, 표준 라이브러리에서 제공하는 std::array는 구조체이기 때문에 배열의 이름이 포인터로 자동으로 변환되지는 않는다.
• 메모리를 할당할 때 크기가 고정되므로 원소를 더 추가하거나 삭제할 수 없다.
• 인덱스를 통해 원소에 임의 접근(Random access)이 가능하다(EX: int[3] = 5;).

3. 벡터(std::vector)

정의

template<class T, class Allocator = std::allocator<T>> 
class vector;

벡터 std::vector는 동적 크기를 가진 배열을 담은 연속적인(sequence) 컨테이너이다.

std::array가 선언할 때 크기가 고정된다면, std::vector는 요소를 추가 및 삭제할 수 있다.

배열과 마찬가지로 _각 요소는 연속된 메모리 공간에 저장_된다. 따라서 반복자를 통해 접근할 수도 있고, 배열에서 요소에 접근하듯이 오프셋을 통해 접근할 수도 있다.

#include <vector>

...

vector<int> scores;
scores.push_back(1); // scores[0] = 1
scores.push_back(2); // scores[1] = 2
scores.push_back(3); // scores[2] = 3
scores[2] = 1000;

벡터는 메모리를 자동으로 관리해 준다. 자동으로 필요할 때 늘어나고 줄어든다. 크기가 고정되어 정적인 배열과 달리 벡터는 얼마나 더 필요할지 모르니, 벡터는 배열보다 더 크게 메모리 공간을 할당한다. 이렇게 하면 각 요소를 추가할 때마다 메모리를 늘리지 않아도 된다. 다만, 할당된 공간이 꽉 찰 때 메모리 공간을 늘린다.

따라서 크기를 관리하는 변수가 size와 capacity 이렇게 두 개로 나뉜다.

• size는 벡터 내에 들어있는 원소의 개수를 가리킨다.
• capacity는 실제 메모리에 할당된 원소의 개수를 가리킨다.

벡터의 구조

그림으로 표현하면, capacity는 다음에 할당할 메모리까지 미리 할당한 영역이므로 언제나 size보다 크거나 같다(capacity ≥ size).

다만 재할당을 할 때에는 그 자리에서 늘리는 게 아니라 새 메모리 공간을 할당하여 그곳에 복사하는 식이다. 조금 있다가 보겠지만, 그 때문에 비효율적인 부분도 있다.

생성 및 추가

벡터 생성의 형식은 다음과 같다.

std::vector NAME;

혹은, 복사 생성자를 통해 기본 벡터와 같은 크기 및 데이터를 갖는 vector를 생성할 수 있다.

#include <vector>

...

std::vector<int> scores;

scores.push_back(1);
scores.push_back(2);
// scores == { 1, 2 }

std::vector<int> scores1(scores); // scores의 사본

위에서 보면 알겠지만, 마지막 요소를 추가할 때 push_back(<data>) 메서드를 사용한다.

반대로 마지막 요소를 삭제할 땐 pop_back()을 사용한다.

vector의 용량 늘리기

벡터는 재할당 과정에서 상당한 자원이 소모된다.

따라서 reserve 메서드를 통해 원하는 크기만큼 새로운 공간을 재할당할 수도 있다.

형식: reserve(<size>);
예시: scores.reserve(10);

요소 접근

operator[](size_t n);

벡터는 각 요소에 접근할 때에도 배열처럼 할 수 있다. 지정된 요소에 접근할 때 인덱스를 통해 임의로 접근(Random access)할 수 있다.

scores[i] = 3;

반복자를 통해서도 접근할 수 있다. vector는 다른 표준 컨테이너처럼 begin()으로 첫 번째 요소를, end()로 마지막 요소 바로 뒤의 요소를 가리키는 반복자를 반환한다. 이를 통해 아래와 같이 순회를 할 수도 있다.

여기서는 이런 것이 있구나 정도만 적어놨으니, 궁금하다면 따로 찾아보자.

for (vector<int>::const_iterator iter = scores.begin(); iter != scores.end(); ++iter)
{
    cout << *iter << " ";
}

문제점

벡터에는 몇 가지 문제점이 존재한다.

1) 중간에 삽입시 복사가 일어남

벡터는 배열 기반의 자료구조이므로, 중간에 원소를 삽입하면 그 뒷부분을 모두 복사해야 한다.

std::vector<int> numbers;
... // 1, 2, 3을 넣는다.
std::vector<int>::iterator it;
it = numbers.begin(); // numbers의 첫 자리의 반복자를 가져옴

it = numbers.insert(it, 0); // 첫 자리에 0을 삽입한다.

예를 들어 위와 같이 맨 끝자리가 아닌 곳에 숫자를 추가하면, 그 뒷자리의 숫자는 모두 복사가 되므로 비효율적이다.

벡터에서 삽입이 일어나면 그 뒷부분을 모두 복사해서 비효율적이다.

2) 재할당(Reallocation)

미리 할당해 놓은 capacity를 넘어 새로운 원소를 추가하면(insert, push_back) 메모리 공간을 더 크게 재할당한다. 이때, 기존의 원소들을 모두 복사하여 새로 할당한 메모리 공간으로 옮긴다.

벡터는 Capacity를 넘어서 할당하면 재할당을 한다.

예를 들어 capacity가 4이고 꽉 차버린 상태라 하자. 이때, 80이라는 원소를 첫 위치에 삽입하면 재할당이 일어나면서 새로운 메모리 공간을 잡게 된다. 그리고 기존의 벡터 원소들을 새 메모리 공간으로 복사한다.

재할당이 일어날 때마다 많은 시간이 소요되기 때문에 reserve()를 통해 처음부터 적절한 크기로 벡터의 용량을 할당하는 것을 권장한다.

정리하자면 벡터 자료구조의 시간 복잡도는 다음과 같다.

• 임의 접근: O(1)
• 마지막 요소에 대한 삽입/삭제: O(1)
• 요소의 삽입/삭제: O(n). 마지막 요소로부터의 거리에 비례한다.

4. 리스트(std::list)

정의

std::list는 상수 시간에 원소를 삽입하고 삭제할 수 있는 컨테이너이다.

일반적으로 자료구조에서 말하는 이중 연결리스트 혹은 양방향 연결리스트(doubly-linked list)로 구성된다. 연결리스트는 기본적으로 노드 기반으로 데이터를 저장하는 자료구조를 말하는데, 각 노드는 데이터 필드와 다른 노드를 가리키는 링크 필드로 나뉜다.

std::list는 연결리스트에 기반을 두므로 데이터가 메모리 상에 저장되는 위치가 불연속적이다.

전형적인 양방향 연결리스트(출처: Implementation of Doubly Linked List in JavaScript - GeeksforGeeks)

위 그림처럼, 이중 연결리스트는 이전 노드와 다음 노드를 모두 가리킬 수 있는 특징이 있다. std::list는 위 그림의 Head처럼, 양방향 연결리스트의 첫 번째 원소를 front()로 가리킨다.

연결리스트의 특징과 똑같이, std::list는 인덱스를 통한 임의 접근(Random access)을 할 수 없다. 이중 연결리스트는 이전 노드, 다음 노드만을 가리킬 수 있기 때문에 인덱스를 통해 접근할 수 없다. 따라서 std::list는 탐색할 때 원소를 하나씩 넘겨가며 찾아야 한다.

// std::list의 예시
#include <list>
#include <iostream>

int main()
{
    using namespace std;
    list<int> c1;
    list<int>::const_iterator cIter; // 반복자를 통한 탐색

    c1.push_back(10);
    c1.push_back(20);
    c1.push_back(30);

    cout << "c1 =";
    for (auto c : c1)
        cout << " " << c;
    cout << endl;
}

삽입/삭제 함수

새로운 데이터를 삽입하는 함수에는 push_front(), push_back(), insert()가 있다.

• push_front: 시작 지점에 원소를 삽입
• push_back: 마지막에 원소를 삽입
• insert: 현재 반복자가 가리키고 있는 위치에 원소를 삽입

상수 시간에 데이터를 삽입하고 삭제할 수 있다는 특징 덕분에 세 함수 모두 O(1)의 시간 복잡도로 수행된다.

삭제의 경우 pop_front(), pop_back(), erase, remove, remove_if 등이 있다.

• pop_front()는 첫 번째 원소를, pop_back()은 마지막 원소를 삭제한다.
• erase는 인자로 넘긴 반복자가 가리키는 노드를 제거한다.
• remove와 remove_if는 주어진 조건을 만족하는 원소를 모두 삭제한다. 연결리스트는 현재 가리키는 원소만을 삭제할 수 있으므로, 두 함수는 처음부터 끝까지 주어진 std::list를 순회하며 조건에 맞는 원소를 지워나간다.

앞의 세 개는 시간 복잡도가 O(1)이지만 remove, remove_if는 모든 노드를 순회해야 하므로 시간 복잡도가 O(n)이다.

장단점

요소의 삽입, 삭제는 상수 시간 O(1)이 걸린다.

std::list는 연결리스트에 기반을 두는데, 덕분에 어디에서든 데이터를 삽입하고 삭제할 때 속도가 빠르다. 삽입할 때, 삭제할 때 모두 두 노드를 연결하는 링크만을 변경해 주면 되기 때문이다.

다만, 실제로 원하는 요소를 찾아 지우려면 탐색이 느리기 때문에 O(n)의 시간이 걸린다.

반면 벡터와 달리 임의로 접근하는 것이 불가능하므로, 원하는 노드를 탐색할 때 최대 N번의 탐색이 필요하다.

그리고 선형탐색할 때에도 캐시 효과로 인해 불연속적인 메모리의 선형탐색이 연속적인 메모리에서보다 느리기 때문에, 탐색도 느린 편이다. 그 때문에 벡터를 쓰는 게 더 빠른 경우가 많다.

시간 복잡도를 정리하면 다음과 같다.

• 요소의 삽입/삭제: 어디든지 상수 시간 O(1)
• 요소의 탐색: O(N)

 

나머지 std::map, std::unordered_map은 다음 글로 분리했습니다.

참고

POCU 아카데미 'COMP3200: C++ 언매니지드 프로그래밍'

std::array - cppreference.com

C++ 레퍼런스 - std::array (안전한 배열) (modoocode.com)

std::vector - cppreference.com

씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)> (modoocode.com)

std::list - cppreference.com

[C++ STL] std::list (시퀀스 컨테이너) (tistory.com)