컨테이너 개요

목록, 집합, 사전, 대기열 같은 자료구조는 거의 모든 프로그램에 필요합니다. C++ 표준 라이브러리는 이런 자료구조를 클래스 템플릿으로 만들어 제공하며, 이 부분을 흔히 표준 템플릿 라이브러리(STL, Standard Template Library)라고 부릅니다. 직접 구현하지 않고도 검증된 자료구조와 알고리즘을 바로 쓸 수 있습니다.

이 장에서는 STL의 컨테이너, 반복자, 알고리즘, 함수 객체를 차례로 다룹니다. 이 글은 STL의 구성과, 데이터를 담는 컨테이너(container)의 종류, 그리고 쓰임에 맞는 컨테이너를 고르는 기준을 정리합니다.

STL의 구성

위 그림처럼 STL은 세 부분이 맞물려 동작합니다. 컨테이너는 원소를 저장하고 그 수명을 관리하며, 반복자(iterator)는 컨테이너 안의 원소 범위를 가리키고, 알고리즘(algorithm)은 반복자가 가리키는 범위에 정렬이나 검색 같은 연산을 적용합니다. 범위는 포인터와 배열에서 본 반열린 범위 [first, last)로 나타내며, 알고리즘에 비교나 조건을 넘길 때는 함수 객체 같은 호출 가능한 객체를 씁니다.

이렇게 나뉜 덕분에, 알고리즘은 어떤 컨테이너에 담긴 원소인지 몰라도 반복자만 있으면 동작합니다. std::sort 하나로 std::vector와 std::deque를 모두 정렬할 수 있는 이유입니다. 반복자는 반복자에서, 알고리즘은 알고리즘에서 자세히 다룹니다.

컨테이너는 원소의 타입을 템플릿 인수로 받으므로, 다른 타입의 값을 넣으려 하면 컴파일할 때 오류가 납니다. 또 필요한 만큼 스스로 메모리를 늘리고 사라질 때 원소를 정리하므로, 직접 new와 delete를 쓸 필요가 없습니다. 많은 컨테이너가 size(), empty(), clear(), begin(), end() 같은 같은 이름의 멤버를 제공하지만, 모든 컨테이너에 모든 멤버가 있는 것은 아닙니다.

시퀀스 컨테이너

시퀀스 컨테이너(sequence container)는 원소를 넣은 위치의 순서대로 보관합니다. 값의 크기로 저절로 정렬되지는 않으며, 정렬하려면 알고리즘을 따로 적용합니다.

std::vector는 원소가 메모리에 이어져 있어 인덱스 접근이 상수 시간이고, 순회할 때 캐시를 잘 활용해 대부분의 경우 가장 빠릅니다. 끝에 추가하는 것은 평균 상수 시간이지만, 중간에 넣거나 지우면 뒤의 원소를 모두 옮겨야 하므로 원소 수에 비례하는 시간이 듭니다. std::list는 어느 위치든 반복자가 있으면 상수 시간에 넣고 지울 수 있지만, 그 위치를 찾으려면 앞에서부터 순회해야 하고 노드마다 포인터 두 개를 더 씁니다.

연관 컨테이너와 비정렬 연관 컨테이너

연관 컨테이너(associative container)는 원소를 키(key)의 순서로 보관해, 키로 빠르게 찾게 합니다. 보통 균형 이진 트리로 구현되어 검색, 삽입, 삭제가 로그 시간이며, 순회하면 키의 순서대로 나옵니다.

C++11부터는 해시 테이블로 만든 비정렬 연관 컨테이너(unordered associative container)인 std::unordered_set, std::unordered_map과 그 multi 버전이 있으며, 헤더는 <unordered_set>과 <unordered_map>입니다. 키의 순서를 지키지 않는 대신 검색, 삽입, 삭제가 평균 상수 시간입니다. 다만 해시 값이 한쪽으로 몰리면 최악에는 원소 수에 비례하는 시간이 들고, 순회 순서는 정해져 있지 않습니다.

더 깊이: 표준이 정한 것과 구현이 고른 자료구조

표준은 연관 컨테이너의 자료구조를 직접 정하지 않고, 연산의 시간 복잡도와 반복자가 무효가 되는 규칙을 정합니다. 그 조건을 만족하는 흔한 방법이 균형 이진 트리여서, GCC의 libstdc++는 stl_tree.h의 레드-블랙 트리(red-black tree)로 std::set과 std::map을 구현합니다. 본문에서 보통 균형 이진 트리로 구현된다고 한 것은 이런 구현의 선택을 말한 것입니다.

비정렬 연관 컨테이너에도 구현을 좁히는 규칙이 있습니다. 원소를 넣다가 재해시가 일어나면 반복자는 모두 무효가 되지만, 원소의 키와 값을 가리키는 참조와 포인터는 그 원소를 지울 때까지 유효해야 합니다. 그래서 원소를 노드로 따로 할당해 버킷(bucket)에 매달아 두는 방식이 자연스럽고, 원소를 하나의 배열에 직접 담아 두었다가 재해시 때 옮기는 방식으로는 이 규칙을 지키기 어렵습니다. 버킷 하나에 담긴 원소 수의 평균인 부하율의 상한 max_load_factor()는 표준이 기본값을 1.0으로 정해 두었으며, 원소가 늘어 부하율이 이 값을 넘으면 컨테이너가 버킷 수를 늘려 재해시합니다.

컨테이너 어댑터

컨테이너 어댑터(container adapter)는 다른 컨테이너 위에 만들어, 특정 자료구조에 필요한 연산만 노출합니다. 일반 컨테이너처럼 begin()과 end()로 순회할 수는 없습니다.

어댑터의 pop()은 원소를 지우기만 하고 값을 돌려주지 않습니다. 값이 필요하면 비어 있지 않은지 확인한 뒤 top()이나 front()로 읽고 나서 pop()합니다.

같은 데이터를 다른 컨테이너에 담기

같은 입력이라도 어느 컨테이너에 담느냐에 따라 남는 정보가 다릅니다. 다음 프로그램은 작업 번호 7, 4, 7을 네 가지 컨테이너에 함께 담습니다.

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

int main() {
    std::vector<int> arrivals{7, 4, 7};
    std::set<int> unique;
    std::map<int, int> counts;
    std::queue<int> pending;

    for (int id : arrivals) {
        unique.insert(id);
        ++counts[id];
        pending.push(id);
    }

    std::cout << arrivals.size() << ' ' << unique.size() << ' ' << counts[7] << '\n';
    for (int id : unique) {
        std::cout << id << ' ';
    }
    std::cout << '\n';

    std::cout << pending.front() << ' ';
    pending.pop();
    std::cout << pending.front() << '\n';
}

3 2 2
4 7
7 4

vector는 도착한 세 건을 순서대로 모두 남기고, set은 두 번째 7을 넣어도 원소가 늘지 않아 고유한 번호 두 개만 키의 순서로 남깁니다. map의 counts[id]는 키가 없으면 값이 0인 원소를 새로 만들어 주므로, 번호를 만날 때마다 1을 더해 등장 횟수를 셉니다. queue는 먼저 들어온 7을 앞에 두고, pop()으로 지운 뒤에는 그다음의 4가 앞에 옵니다.

컨테이너 고르기

컨테이너는 이름보다, 프로그램에서 가장 자주 하는 연산이 무엇인지로 고릅니다. 아래 그림처럼 키로 찾는 일이 중심이라면 키의 순서가 필요한지에 따라 map과 set 또는 해시 계열을 고르고, 순서대로 저장하는 일이 중심이라면 기본은 vector이며 원소의 위치가 바뀌면 안 되거나 양쪽 끝을 자주 다룰 때 list나 deque를 고릅니다.

특별한 이유가 없다면 std::vector를 기본으로 씁니다. 원소가 적거나 순회가 많다면, 중간 삽입이 이론상 느린 vector가 연결 리스트보다 실제로 빠른 경우도 흔합니다. 표의 시간 복잡도만으로 정하기 어렵다면 실제 데이터로 측정하고, 다음 글에서 볼 반복자가 언제 무효가 되는지도 함께 확인합니다. C++23에는 정렬한 vector 위에 만든 std::flat_map과 std::flat_set도 추가되었습니다.

정리

• STL은 원소를 저장하는 컨테이너, 범위를 가리키는 반복자, 범위에 연산을 적용하는 알고리즘으로 이루어집니다.
• 시퀀스 컨테이너는 넣은 순서대로 보관하며, std::vector가 대부분의 경우 기본 선택입니다.
• 연관 컨테이너는 키의 순서로 보관해 로그 시간에 찾고, 비정렬 연관 컨테이너는 해시로 평균 상수 시간에 찾지만 순서가 없습니다.
• 컨테이너 어댑터는 스택, 큐, 우선순위 큐의 연산만 노출하며, pop()은 값을 돌려주지 않습니다.
• 같은 데이터라도 컨테이너에 따라 순서, 중복, 횟수 가운데 남는 정보가 다르므로, 보존할 정보부터 정합니다.
• 컨테이너는 가장 자주 하는 연산으로 고르고, 성능이 중요하면 실제 데이터로 측정합니다.

연습 문제

1. 입력 바꾸기

four_containers.cpp의 arrivals를 {9, 3, 9, 3, 1}로, 첫 출력의 counts[7]을 counts[9]로 바꾸면 세 줄은 무엇을 출력하나요? 도착 순서와 중복을 모두 보존해야 한다면 set 하나로 충분한가요?

2. 알맞은 컨테이너

다음 세 경우에 알맞은 컨테이너는 무엇인가요? (가) 편집기의 되돌리기 기록에서 가장 최근 작업부터 취소 (나) 문서의 단어별 등장 횟수를 알파벳 순서로 출력 (다) 방문한 주소인지 순서와 상관없이 빠르게 확인

3. 읽기만 했는데 늘어난 원소

four_containers.cpp의 끝에 std::cout << counts[5] << ' ' << counts.size() << '\n';를 추가하면 무엇이 출력되나요? 원소를 늘리지 않고 키 5가 있는지만 확인하려면 어떻게 하나요?

다음 글 반복자에서는 컨테이너의 원소를 가리키고 순회하는 반복자의 종류와, 컨테이너를 바꿀 때 반복자가 무효가 되는 규칙을 다룹니다.