C++ vector vs list vs deque: 내부 구조와 벤치마크로 보는 컨테이너 선택
이 글의 핵심
빅오 표기만 보고 list를 골랐다가 오히려 느려지는 상황에서 출발합니다. 원소당 메모리 오버헤드, 원소 개수에 따라 달라지는 성능 차이, 게임 엔티티 관리와 텍스트 에디터 버퍼, 우선순위 큐 사례를 거쳐 상황별로 어떤 컨테이너를 고를지 결정 트리로 정리합니다.
들어가며: “vector, list, deque… 뭘 써야 하죠?”
C++ STL은 vector, list, deque 세 가지 주요 시퀀스 컨테이너를 제공합니다. 각각 시간 복잡도와 메모리 레이아웃이 다르므로, 상황에 맞는 선택이 중요합니다.
언제 vector를, 언제 list·deque를 쓰나요?
| 관점 | vector | list | deque |
|---|---|---|---|
| 성능 | 순차 접근·캐시 최우수 | 중간 삽입 이론상 O(1)이나 상수·할당 비용 큼 | 양끝 삽입·삭제 O(1) |
| 사용성 | [], reserve 등 직관적 | 노드 기반 반복자 무효 규칙 주의 | 인덱스 접근은 vector보다 제약 |
| 적용 시나리오 | 기본 선택 | 삽입 위치가 정말 임의로 많을 때 | 슬라이딩 윈도·양쪽 큐 |
흔한 오해도 몇 가지 있습니다. 중간 삽입이 많다고 해서 list가 자동으로 정답이 되지는 않습니다. 삽입 위치를 찾는 비용과 노드 할당 비용, 캐시 효율까지 따지면 vector가 이기는 경우가 많습니다. deque는 양쪽 끝 삽입만 빠른 것이 아니라 인덱스 접근도 O(1)이지만, 청크를 거치는 간접 참조 때문에 vector보다는 느립니다.
이 글은 vector·list·deque의 내부 구조와 삽입·삭제·조회 복잡도를 비교하고, 캐시 효율이 드러나는 실제 벤치마크와 메모리 사용량을 근거로 상황별 선택 기준을 정리합니다.
컨테이너 내부 구조
vector: 연속 메모리 배열
[1][2][3][4][5][6][7][8]...
↑ ↑
begin end
특징:
- 연속된 메모리 블록
- 캐시 효율 최고
- 재할당 시 전체 복사std::vector<int> vec = {1, 2, 3, 4, 5};
// 메모리 레이아웃
// [1][2][3][4][5][capacity 여유 공간...]list: 이중 연결 리스트
[1] ⇄ [2] ⇄ [3] ⇄ [4] ⇄ [5]
↑ ↑
begin end
특징:
- 노드가 메모리에 흩어짐
- 각 노드는 prev/next 포인터 보유
- 재할당 없음std::list<int> lst = {1, 2, 3, 4, 5};
// 메모리 레이아웃 (개념적)
// Node1: [prev=null][data=1][next=Node2]
// Node2: [prev=Node1][data=2][next=Node3]
// ...deque: 청크 배열
청크1: [1][2][3][4]
청크2: [5][6][7][8]
청크3: [9][10][11][12]
↑
map (청크 포인터 배열)
특징:
- 여러 고정 크기 청크
- 양쪽 끝 삽입 O(1)
- 중간 접근 O(1) (약간 느림)시간 복잡도 비교
연산별 시간 복잡도
| 연산 | vector | list | deque |
|---|---|---|---|
| 앞쪽 삽입 | O(n) | O(1) | O(1) |
| 뒤쪽 삽입 | O(1) 분할상환 | O(1) | O(1) |
| 중간 삽입 | O(n) | O(1) | O(n) |
| 앞쪽 삭제 | O(n) | O(1) | O(1) |
| 뒤쪽 삭제 | O(1) | O(1) | O(1) |
| 중간 삭제 | O(n) | O(1) | O(n) |
| 인덱스 접근 | O(1) | O(n) | O(1) |
| 순차 순회 | 빠름 | 느림 | 중간 |
| 메모리 효율 | 높음 | 낮음 | 중간 |
주의: 시간 복잡도 ≠ 실제 성능
캐시 효율이 실제 성능에 큰 영향을 줍니다.
// list: O(1) 삽입
std::list<int> lst;
for (int i = 0; i < 1000000; ++i) {
lst.push_back(i); // O(1), 하지만 캐시 미스 다발
}
// vector: O(1) 분할상환 삽입
std::vector<int> vec;
vec.reserve(1000000);
for (int i = 0; i < 1000000; ++i) {
vec.push_back(i); // O(1), 캐시 효율 높음
}
// 실제 성능: 둘 다 O(1)이지만 vector가 크게 앞섬차이는 할당 횟수에서 나옵니다. list는 원소 하나마다 new로 노드를 할당하므로 100만 번 할당하고, vector는 reserve 덕분에 한 번만 할당합니다. 할당자가 빠를수록, 원소 타입이 클수록 이 격차는 줄어듭니다.
실제 성능 벤치마크
이 절에서는 각 테스트의 코드와 함께, 결과가 어느 쪽으로 나오는지와 그 이유를 설명합니다. 절대 시간은 CPU·할당자·컴파일러에 따라 몇 배씩 달라지므로 싣지 않았습니다. 아래 완전한 벤치마크 코드를 -O2 이상으로 빌드해 자기 환경에서 직접 돌려 보면 순서와 대략적인 격차를 확인할 수 있습니다.
테스트 1: 뒤쪽 삽입 (push_back)
// 벤치마크 코드
template <typename Container>
void benchPushBack() {
Container c;
for (int i = 0; i < 1000000; ++i) {
c.push_back(i);
}
}예상되는 순서: vector(reserve) ≤ vector < deque < list
분석: vector는 재할당이 약 20번(2배 성장 기준 log₂ 100만)뿐이고, reserve를 쓰면 그마저 없어집니다. deque는 청크가 찰 때마다 새 청크를 할당하므로 vector보다 할당이 많고, list는 원소마다 노드를 할당하므로 가장 느립니다. 격차의 크기는 사실상 할당 횟수 × 할당자 속도로 정해집니다.
테스트 2: 앞쪽 삽입 (push_front)
template <typename Container>
void benchPushFront() {
Container c;
for (int i = 0; i < 100000; ++i) { // 10만 개 (100만은 너무 느림)
c.push_front(i);
}
}예상되는 순서: deque < list ≪ vector (vector는 push_front가 없어 insert(begin())로 측정)
분석: vector 앞쪽 삽입은 매번 기존 원소 전부를 한 칸씩 밀어야 하므로 전체 비용이 O(n²)입니다. 원소 수를 두 배로 늘리면 시간이 약 네 배가 되는 식으로, n이 커질수록 다른 두 컨테이너와의 격차가 폭발적으로 벌어집니다. deque는 앞쪽에도 청크를 붙이므로 O(1)이고, list보다 할당 횟수가 적어 보통 가장 빠릅니다.
테스트 3: 중간 삽입
template <typename Container>
void benchMiddleInsert() {
Container c;
// 초기 데이터
for (int i = 0; i < 10000; ++i) {
c.push_back(i);
}
// 중간에 1000번 삽입
auto it = c.begin();
std::advance(it, 5000); // 중간 위치
for (int i = 0; i < 1000; ++i) {
it = c.insert(it, 999); // vector/deque는 insert 후 기존 반복자가 무효화되므로 반환값으로 갱신
}
}분석: 이 테스트는 결과가 조건에 가장 민감합니다. 삽입 위치를 이미 알고 있다면 list의 삽입은 O(1)이고, vector는 위치 뒤의 원소를 memmove로 밀어야 하므로 O(n)입니다. 그런데 int 5천 개(20KB)를 미는 memmove는 캐시 안에서 연속으로 처리되어 매우 빠르고, list는 삽입마다 노드를 할당합니다. 그래서 이 정도 크기에서는 vector가 list와 비슷하거나 더 빠른 경우가 흔합니다. 원소 수가 캐시를 크게 넘거나 원소 이동 비용이 큰 타입일수록 list 쪽이 유리해집니다.
또 하나 중요한 점은 삽입 위치를 찾는 비용입니다. 실제 코드에서는 위치를 탐색해야 하는 경우가 많은데, list는 그 탐색이 포인터를 따라가는 O(n)이고 캐시 미스가 연속으로 나므로, 탐색까지 포함하면 list의 이점은 대부분 사라집니다.
테스트 4: 순차 순회
template <typename Container>
void benchIteration(const Container& c) {
long long sum = 0;
for (int x : c) {
sum += x;
}
}예상되는 순서: vector < deque < list
분석: vector는 연속 메모리라 하드웨어 프리페처가 다음 캐시 라인을 미리 가져오고, 컴파일러가 SIMD로 벡터화할 수도 있습니다. deque는 청크 경계마다 한 번씩 간접 참조가 끼어듭니다. list는 다음 노드 주소를 알아야 다음 읽기를 시작할 수 있어 메모리 지연이 그대로 드러납니다. 방금 순서대로 할당한 list는 노드가 메모리에 비교적 가지런히 놓여 격차가 작게 나오지만, 삽입·삭제를 반복해 노드가 흩어진 list에서는 격차가 훨씬 커집니다.
테스트 5: 랜덤 접근
template <typename Container>
void benchRandomAccess(Container& c) {
for (int i = 0; i < 100000; ++i) {
int idx = rand() % c.size();
int x = c[idx]; // list는 operator[] 없음
}
}분석: vector는 주소 계산 한 번이면 되고, deque는 “몇 번째 청크의 몇 번째 원소”를 계산하는 간접 참조가 한 단계 더 있어 약간 느립니다. list는 operator[]가 없고, std::next로 흉내 내면 O(n)이라 비교 대상이 아닙니다. 참고로 rand() 호출 비용이 접근 비용과 비슷해서 이 코드로는 차이가 작게 보일 수 있습니다.
메모리 사용량 비교
원소당 오버헤드
// int 하나를 저장할 때 실제 메모리 사용량
// vector<int>
// [4바이트] + (재할당 여유 공간)
// 오버헤드: 거의 없음 (capacity > size일 때만)
// list<int>
// [8바이트 prev][8바이트 next][4바이트 데이터 + 4바이트 패딩] = 24바이트
// + malloc 헤더/최소 청크 크기 → 실제로는 원소당 32바이트 안팎
// deque<int>
// [4바이트] + (청크 포인터 배열 오버헤드)
// 오버헤드: 약간 (청크 크기에 따라)100만 개 int 저장 시 메모리
| 컨테이너 | 대략적인 메모리 사용량 | 계산 근거 |
|---|---|---|
| vector (reserve) | 약 4MB | 100만 × 4바이트 |
| vector (reserve 없이) | 약 4.2MB, 재할당 순간 최대 약 6MB | 2배 성장 시 capacity가 1,048,576이 되고, 재할당 중에는 이전 버퍼와 새 버퍼가 잠시 공존 |
| list | 약 24~32MB | 노드 24바이트 + 할당자 오버헤드 |
| deque | 약 4MB + 청크 포인터 배열 | 청크에 원소가 빽빽이 들어가고 map 배열만 추가 |
원소가 작을수록 list의 노드 오버헤드 비중이 커집니다. int처럼 작은 원소라면 list는 vector보다 6~8배 정도의 메모리를 씁니다.
상황별 선택 가이드
결정 트리
Q1. 랜덤 접근이 필요한가?
Yes → vector 또는 deque
No → Q2
Q2. 중간 삽입/삭제가 매우 빈번한가?
Yes → 위치를 이미 알고 있고 원소가 크면 list, 아니면 vector부터 측정
No → Q3
Q3. 앞쪽 삽입/삭제가 빈번한가?
Yes → deque
No → vector상황별 권장
| 상황 | 권장 | 이유 |
|---|---|---|
| 기본 선택 | vector | 캐시 효율, 메모리 효율 최고 |
| 뒤쪽만 추가 | vector | push_back O(1) 분할상환 |
| 앞쪽 추가/삭제 | deque | push_front O(1) |
| 양쪽 끝 추가/삭제 | deque | 큐, 덱 자료구조 |
| 중간 삽입/삭제 빈번 | list (측정 후) | 위치를 이미 알고 있고 원소 수·크기가 클 때 유리 |
| 랜덤 접근 빈번 | vector | operator[] O(1) |
| 순차 순회 빈번 | vector | 캐시 효율 최고 |
| 메모리 절약 | vector | 오버헤드 최소 |
| 반복자 무효화 회피 | list | 삽입/삭제 시 반복자 유지 |
실전 예제
예제 1: 로그 버퍼
// 요구사항: 뒤에 계속 추가, 가끔 전체 순회
// 권장: vector
std::vector<LogEntry> logs;
logs.reserve(10000); // 재할당 방지
logs.push_back(entry); // O(1)
// 순회 (매우 빠름)
for (const auto& log : logs) {
// ...
}예제 2: 작업 큐 (양쪽 끝 접근)
// 요구사항: 앞에서 꺼내고, 뒤에 추가
// 권장: deque
std::deque<Task> tasks;
tasks.push_back(task); // 뒤에 추가 O(1)
Task t = tasks.front(); // 앞에서 조회 O(1)
tasks.pop_front(); // 앞에서 제거 O(1)예제 3: LRU 캐시
list가 제 역할을 하는 대표적인 경우입니다. 해시맵이 리스트 노드의 반복자를 들고 있어 위치를 탐색할 필요가 없고, list의 반복자는 다른 원소의 삽입·삭제에도 무효화되지 않기 때문입니다.
struct CacheEntry { Key key; Value value; };
std::list<CacheEntry> lru; // 앞쪽이 가장 오래된 항목
std::unordered_map<Key, std::list<CacheEntry>::iterator> cache;
// 조회한 항목을 맨 뒤(최근)로 옮김: 노드 재할당 없이 O(1), 반복자도 그대로 유효
auto it = cache.at(key);
lru.splice(lru.end(), lru, it);
// 용량 초과 시 가장 오래된 항목 제거
cache.erase(lru.front().key);
lru.pop_front();예제 4: 정렬된 데이터 유지
// 요구사항: 정렬 유지, 이진 탐색
// 권장: vector
std::vector<int> sorted_data;
// 삽입 (이진 탐색 + 삽입)
auto it = std::lower_bound(sorted_data.begin(), sorted_data.end(), value);
sorted_data.insert(it, value); // O(n), 하지만 캐시 효율로 빠름
// 이진 탐색 O(log n)
bool found = std::binary_search(sorted_data.begin(), sorted_data.end(), value);완전한 벤치마크 코드
직접 실행해볼 수 있는 완전한 벤치마크 코드입니다.
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <chrono>
#include <algorithm>
#include <iomanip>
#include <type_traits>
using namespace std;
using namespace chrono;
// 벤치마크 헬퍼
template <typename Func>
double measureTime(Func&& func) {
auto start = steady_clock::now();
func();
auto end = steady_clock::now();
return duration_cast<microseconds>(end - start).count() / 1000.0;
}
// 1. 뒤쪽 삽입 벤치마크
template <typename Container>
double benchPushBack(int n) {
return measureTime([n]() {
Container c;
for (int i = 0; i < n; ++i) {
c.push_back(i);
}
});
}
// 2. 앞쪽 삽입 벤치마크 (vector는 push_front 없으므로 insert 사용)
template <typename Container>
double benchPushFront(int n) {
return measureTime([n]() {
Container c;
for (int i = 0; i < n; ++i) {
if constexpr (is_same_v<Container, vector<int>>) {
c.insert(c.begin(), i);
} else {
c.push_front(i);
}
}
});
}
// 3. 중간 삽입 벤치마크
template <typename Container>
double benchMiddleInsert(int n, int insertCount) {
return measureTime([n, insertCount]() {
Container c;
// 초기 데이터
for (int i = 0; i < n; ++i) {
c.push_back(i);
}
// 중간 위치 찾기
auto it = c.begin();
advance(it, n / 2);
// 중간에 삽입
for (int i = 0; i < insertCount; ++i) {
it = c.insert(it, 999); // 반복자 무효화 방지
}
});
}
// 4. 순차 순회 벤치마크
template <typename Container>
double benchIteration(const Container& c) {
return measureTime([&c]() {
long long sum = 0;
for (int x : c) {
sum += x;
}
// 최적화 방지
volatile long long result = sum;
});
}
int main() {
cout << "=== C++ 컨테이너 성능 벤치마크 ===" << endl << endl;
// 1. 뒤쪽 삽입 (100만 개)
cout << "1. 뒤쪽 삽입 (push_back) - 100만 개" << endl;
cout << " vector: " << fixed << setprecision(2)
<< benchPushBack<vector<int>>(1000000) << " ms" << endl;
cout << " list: " << benchPushBack<list<int>>(1000000) << " ms" << endl;
cout << " deque: " << benchPushBack<deque<int>>(1000000) << " ms" << endl;
cout << endl;
// 2. 앞쪽 삽입 (10만 개 - vector는 너무 느려서)
cout << "2. 앞쪽 삽입 (push_front) - 10만 개" << endl;
cout << " vector: " << benchPushFront<vector<int>>(100000) << " ms" << endl;
cout << " list: " << benchPushFront<list<int>>(100000) << " ms" << endl;
cout << " deque: " << benchPushFront<deque<int>>(100000) << " ms" << endl;
cout << endl;
// 3. 중간 삽입 (1만 개 초기 + 1000번 삽입)
cout << "3. 중간 삽입 - 1만 개 초기, 1000번 삽입" << endl;
cout << " vector: " << benchMiddleInsert<vector<int>>(10000, 1000) << " ms" << endl;
cout << " list: " << benchMiddleInsert<list<int>>(10000, 1000) << " ms" << endl;
cout << " deque: " << benchMiddleInsert<deque<int>>(10000, 1000) << " ms" << endl;
cout << endl;
// 4. 순차 순회 (100만 개)
cout << "4. 순차 순회 - 100만 개" << endl;
vector<int> vec(1000000);
list<int> lst(1000000);
deque<int> deq(1000000);
cout << " vector: " << benchIteration(vec) << " ms" << endl;
cout << " list: " << benchIteration(lst) << " ms" << endl;
cout << " deque: " << benchIteration(deq) << " ms" << endl;
cout << endl;
cout << "=== 결론 ===" << endl;
cout << "- 대부분의 경우: vector 사용" << endl;
cout << "- 앞쪽 삽입/삭제: deque 사용" << endl;
cout << "- 중간 삽입 매우 빈번 + 원소 많음: list 고려" << endl;
return 0;
}컴파일 및 실행:
g++ -std=c++17 -O3 -o bench benchmark.cpp
./bench결과를 읽는 법: 절대 시간은 환경마다 다르므로 컨테이너 사이의 순서와 비율을 보세요. 뒤쪽 삽입과 순회에서는 vector가 앞서고, 앞쪽 삽입에서는 vector만 원소 수에 따라 급격히 느려지며, 중간 삽입은 원소 수와 원소 크기에 따라 순서가 바뀔 수 있습니다. 한 번만 돌리지 말고 여러 번 반복해 중앙값을 보고, 결과를 쓰지 않는 루프는 컴파일러가 통째로 지울 수 있다는 점(순회 코드가 sum을 volatile 변수에 쓰는 이유)도 확인하세요. 삽입 벤치마크도 같은 이유로 최적화 수준에 따라 일부가 제거될 수 있으니, 정밀하게 재려면 아래 Google Benchmark처럼 최적화 방지 장치가 있는 도구를 쓰는 편이 낫습니다.
벤치마크 상세 분석
원소 개수에 따라 결론이 바뀌는 이유
중간 삽입에서 vector의 비용은 “뒤로 밀어야 하는 바이트 수”에 비례하고, list의 비용은 “노드 할당 한 번”으로 거의 일정합니다. 원소가 적으면 밀어야 할 바이트가 적고 전부 캐시 안에 있어 vector가 이기고, 원소 수가 커져 한 번의 삽입마다 수 MB를 옮겨야 하는 크기가 되면 list가 앞서기 시작합니다. 둘이 역전되는 지점은 원소 크기, 할당자, CPU 캐시 크기에 따라 달라지므로 “몇 개부터 list”라는 고정된 기준은 없습니다. 삽입 위치를 탐색하는 비용까지 포함하면 역전 지점은 훨씬 뒤로 밀립니다.
캐시 효율 측정
# perf로 캐시 미스 측정
perf stat -e cache-misses,cache-references ./bench_vector
perf stat -e cache-misses,cache-references ./bench_list보는 법: cache-misses를 cache-references로 나눈 미스율을 비교합니다. vector 순회는 프리페처 덕분에 미스율이 낮게 나오고, 노드가 흩어진 list는 노드마다 미스가 날 수 있어 미스율이 크게 올라갑니다. 다만 이 카운터가 정확히 어떤 캐시 레벨을 세는지는 CPU마다 달라서, 서로 다른 머신의 수치를 비교하기보다는 같은 머신에서 컨테이너끼리 비교하는 용도로 쓰는 것이 맞습니다.
실전 사례 분석
사례 1: 게임 엔티티 관리
엔티티는 자주 추가·삭제되지만, 그보다 훨씬 자주 일어나는 일은 매 프레임 전체를 순회하는 것입니다. 그래서 순회가 빠른 vector를 고르고, 삭제는 순서를 포기하는 대신 O(1)로 끝나는 swap-and-pop으로 처리합니다.
class EntityManager {
std::vector<Entity> entities_;
public:
void add(Entity e) {
entities_.push_back(e);
}
void remove(EntityId id) {
// 찾기는 O(n), 제거 자체는 swap-and-pop으로 O(1) (순서 유지 안 함)
// 실제 엔진은 id → 인덱스 맵을 두어 찾기도 O(1)로 만듦
auto it = std::find_if(entities_.begin(), entities_.end(),
[id](const Entity& e) { return e.id == id; });
if (it != entities_.end()) {
if (it != std::prev(entities_.end())) {
*it = std::move(entities_.back()); // 자기 자신으로의 이동 대입 방지
}
entities_.pop_back();
}
}
void update() {
for (auto& e : entities_) { // 캐시 효율 최고
e.update();
}
}
};사례 2: 텍스트 에디터 버퍼
타이핑은 커서 위치에서의 삽입·삭제가 연속으로 일어나고, 화면 렌더링은 순차 접근입니다. 아래는 deque로 만든 단순한 버퍼입니다.
class TextBuffer {
std::deque<char> buffer_;
public:
void insert(size_t pos, char c) {
auto it = buffer_.begin();
std::advance(it, pos);
buffer_.insert(it, c); // 중간 삽입
}
void erase(size_t pos) {
auto it = buffer_.begin();
std::advance(it, pos);
buffer_.erase(it);
}
std::string getText() const {
return std::string(buffer_.begin(), buffer_.end());
}
};deque의 중간 삽입은 가까운 쪽 끝까지의 원소를 미는 O(min(pos, n−pos)) 연산이라, 짧은 문서에서는 충분하지만 큰 파일의 한가운데를 편집하면 키 입력마다 많은 원소를 옮깁니다. 실제 에디터는 커서 위치에 빈 공간을 두는 갭 버퍼(Emacs), 원본과 추가분을 조각 목록으로 관리하는 피스 테이블(VS Code), 트리 기반의 로프 같은 전용 구조를 씁니다. list는 커서 이동과 렌더링 순회가 느려 이 용도에도 잘 맞지 않습니다.
사례 3: 우선순위 큐
최댓값을 빠르게 꺼내야 하는 우선순위 큐는 vector 위에 힙 알고리즘을 올려 구현합니다.
#include <algorithm>
#include <queue>
#include <vector>
std::vector<int> heap;
// 삽입 O(log n)
heap.push_back(value);
std::push_heap(heap.begin(), heap.end());
// 최댓값 조회 O(1)
int max = heap.front();
// 최댓값 제거 O(log n)
std::pop_heap(heap.begin(), heap.end());
heap.pop_back();
// 또는 std::priority_queue 사용 (내부적으로 vector + heap)
std::priority_queue<int> pq;힙은 부모와 자식의 위치를 인덱스 계산(2i+1, 2i+2)으로 찾으므로 연속 메모리 배열에 자연스럽게 맞습니다.
고급 최적화 기법
vector 성능 극대화
// 1. reserve로 재할당 방지
vector<int> vec;
vec.reserve(1000000); // 미리 메모리 확보
for (int i = 0; i < 1000000; ++i) {
vec.push_back(i); // 재할당 없음 → 빠름
}
// 2. emplace_back으로 복사 방지
vector<string> strs;
strs.reserve(1000);
strs.emplace_back("hello"); // 직접 생성 (복사 없음)
// 3. shrink_to_fit으로 메모리 절약
vec.clear();
vec.shrink_to_fit(); // 여유 메모리 반환 요청 (구속력 없는 요청이지만 주요 구현은 실제로 줄임)list 최적화: splice 활용
// list의 강점: O(1) splice (노드 이동)
list<int> list1 = {1, 2, 3};
list<int> list2 = {4, 5, 6};
// list2의 모든 원소를 list1 끝으로 이동 - O(1)!
list1.splice(list1.end(), list2);
// list1: [1, 2, 3, 4, 5, 6]
// list2: [] (비어있음)
// vector로 하면 O(n) 복사 필요
vector<int> vec1 = {1, 2, 3};
vector<int> vec2 = {4, 5, 6};
vec1.insert(vec1.end(), vec2.begin(), vec2.end()); // O(n) 복사deque 메모리 레이아웃 이해
// deque는 청크 단위로 메모리를 할당
deque<int> deq;
deq.push_back(1); // 첫 청크 할당
deq.push_front(0); // 첫 청크 앞쪽에 빈 칸이 없으면 새 청크를 앞에 할당
// 청크 포인터 배열(map)은 가운데 칸부터 사용하므로
// 앞뒤 어느 쪽으로든 청크를 붙일 여유가 있음
// map: [ ][ ][청크A][청크B][ ][ ]청크 안에서 첫 원소가 놓이는 위치는 구현마다 다릅니다. 공통점은 map이 꽉 차기 전까지는 기존 원소를 옮기지 않고 청크만 추가한다는 점이며, 그래서 양쪽 끝 삽입이 원소 이동 없이 O(1)에 끝납니다. map이 꽉 차면 포인터 배열만 재할당하고 원소 자체는 이동하지 않습니다.
흔한 실수와 해결책
실수 1: list를 기본으로 사용
// ❌ 나쁜 예: 이유 없이 list 사용
list<Player> players;
for (auto& p : players) { // 캐시 미스 다발
p.update();
}
// ✅ 좋은 예: vector 사용
vector<Player> players;
players.reserve(1000);
for (auto& p : players) { // 캐시 효율 최고
p.update();
}이유: 매 프레임 순회하는 코드에서는 노드를 따라가는 list의 메모리 지연이 매번 반복되므로, 연속 메모리인 vector가 크게 유리합니다.
실수 2: vector reserve 안 함
// ❌ 나쁜 예: 재할당 다발
vector<int> vec;
for (int i = 0; i < 1000000; ++i) {
vec.push_back(i); // 재할당 20번 발생
}
// ✅ 좋은 예: 미리 reserve
vector<int> vec;
vec.reserve(1000000); // 재할당 0번
for (int i = 0; i < 1000000; ++i) {
vec.push_back(i);
}성능 차이: 재할당 약 20번과 그때마다의 원소 복사가 사라집니다. int처럼 복사가 싼 타입에서는 차이가 크지 않고, 원소가 크거나 복사 비용이 클수록 효과가 커집니다. 재할당 때문에 반복자·포인터가 무효화되는 문제를 피하는 것도 reserve의 중요한 이유입니다.
실수 3: deque를 vector처럼 사용
// ❌ 나쁜 예: deque를 단순 배열로 사용
deque<int> deq;
for (int i = 0; i < 1000000; ++i) {
deq.push_back(i); // 청크 할당·간접 참조 때문에 보통 vector보다 느림
}
// ✅ 좋은 예: 양쪽 끝 접근이 필요할 때만 deque
deque<int> deq;
deq.push_front(1); // 앞쪽 삽입 O(1)
deq.push_back(2); // 뒤쪽 삽입 O(1)성능 측정 도구
Google Benchmark 사용
#include <benchmark/benchmark.h>
#include <vector>
#include <list>
#include <deque>
static void BM_VectorPushBack(benchmark::State& state) {
for (auto _ : state) {
std::vector<int> vec;
for (int i = 0; i < state.range(0); ++i) {
vec.push_back(i);
}
benchmark::DoNotOptimize(vec.data());
benchmark::ClobberMemory();
}
}
BENCHMARK(BM_VectorPushBack)->Range(1000, 1000000);
static void BM_ListPushBack(benchmark::State& state) {
for (auto _ : state) {
std::list<int> lst;
for (int i = 0; i < state.range(0); ++i) {
lst.push_back(i);
}
benchmark::DoNotOptimize(lst);
benchmark::ClobberMemory();
}
}
BENCHMARK(BM_ListPushBack)->Range(1000, 1000000);
BENCHMARK_MAIN();DoNotOptimize와 ClobberMemory는 컴파일러가 결과를 쓰지 않는 루프를 제거하지 못하게 막습니다. 캐시 미스 측정은 앞의 perf stat 명령을 그대로 쓰면 됩니다.
그 밖의 비교 포인트
정렬: list::sort vs std::sort
list는 임의 접근 반복자가 없어 std::sort를 쓸 수 없고 멤버 함수 sort()(병합 정렬)를 씁니다. 복잡도는 둘 다 O(n log n)이지만, 노드를 따라가며 정렬하는 list보다 연속 메모리에서 도는 vector + std::sort가 보통 훨씬 빠릅니다. list를 정렬해야 한다면 vector로 복사해 정렬한 뒤 다시 채우는 편이 빠를 때도 있습니다. 다만 list::sort는 노드를 이동하지 않고 링크만 바꾸므로 기존 반복자가 유효하게 남는다는 장점이 있습니다.
// vector: O(n log n), 캐시 효율 높음
vector<int> vec = {3, 1, 4, 1, 5};
std::sort(vec.begin(), vec.end()); // 매우 빠름
// list: O(n log n), 캐시 미스 많음
list<int> lst = {3, 1, 4, 1, 5};
lst.sort(); // 노드를 따라가는 병합 정렬이라 보통 vector + std::sort보다 느림큰 연속 메모리가 부담될 때
vector는 전체 원소를 하나의 연속 블록에 두므로, 크기가 아주 커지면 그만한 연속 공간을 찾아야 하고 재할당 중에는 이전 버퍼와 새 버퍼가 잠깐 함께 존재합니다. deque는 고정 크기 청크를 여러 개 할당하므로 큰 연속 블록이 필요 없고 성장 중에도 원소를 옮기지 않습니다.
// vector: 4MB 연속 블록 하나
vector<int> vec;
vec.reserve(1000000);
// deque: 작은 청크 여러 개 (libstdc++ 기준 512바이트 청크)
deque<int> deq;멀티스레드 환경
세 컨테이너 모두 같은 규칙을 따릅니다. 여러 스레드가 const 멤버 함수로 동시에 읽기만 하는 것은 안전하지만, 한 스레드라도 수정한다면 모든 접근을 std::mutex 같은 동기화로 보호해야 합니다. 공유가 필요 없다면 스레드마다 따로 두는 편이 가장 간단합니다.
// 방법 1: mutex로 보호
mutex mtx;
vector<int> shared_vec;
void producer() {
lock_guard<mutex> lock(mtx);
shared_vec.push_back(42);
}
// 방법 2: thread-local 사용
thread_local vector<int> local_vec;
void worker() {
local_vec.push_back(42); // 스레드마다 별도 객체라 락 불필요
}