C++ STL 컨테이너: 연산별 성능 비교와 상황별 선택 기준
이 글의 핵심
STL 컨테이너의 내부 동작과 성능 차이를 반복자 무효화, 메모리 레이아웃, 캐시 성능, 벤치마크, 프로덕션 튜닝 관점에서 정리합니다.
들어가며: 캐시 성능이 Big-O를 이긴다
STL 컨테이너를 고를 때 흔히 시간 복잡도 표를 먼저 봅니다. vector는 중간 삽입이 O(n), list는 O(1)이니 삽입이 잦으면 list가 낫다고 생각하기 쉽지만, 실제로는 그렇지 않은 경우가 많습니다. list에서도 삽입할 위치를 찾으려면 노드를 하나씩 따라가야 하고, 그 순회가 vector의 원소 이동보다 비싸기 때문입니다.
현대 CPU에서는 캐시 성능이 이론적 복잡도만큼, 때로는 그보다 더 중요합니다. 같은 원소 10만 개를 순회해도 vector, list, map은 모두 O(n)이지만, 실제로 재 보면 vector가 가장 빠르고 list와 map은 그보다 몇 배 이상 느리게 나오는 것이 보통입니다.
왜 이런 차이가 날까요? 캐시 미스 때문입니다. 캐시를 모두 놓치고 메인 메모리까지 가는 접근은 L1 캐시 적중보다 수십 배 이상 느립니다. vector는 연속 메모리라 캐시 라인(64바이트)을 최대한 활용하지만, list와 map은 포인터를 따라가며 캐시 미스를 유발합니다.
이 글은 STL 컨테이너의 내부 메커니즘부터 실전 최적화까지 순서대로 살펴봅니다.
캐시와 메모리 계층 이해
현대 CPU의 메모리 계층
CPU 레지스터
↓ ~1 cycle
L1 캐시 (32-64KB)
↓ ~4 cycles
L2 캐시 (256KB-1MB)
↓ ~12 cycles
L3 캐시 (8-32MB, 코어 간 공유)
↓ ~40 cycles
메인 메모리 (GB)
↓ 수백 cycles위 사이클 수는 CPU 세대마다 달라지는 대략적인 크기 비교용 값입니다. 핵심: 메인 메모리까지 가는 캐시 미스 한 번은 수백 사이클을 잃을 수 있습니다. 데이터를 순차적으로 접근하면 캐시 프리페칭(prefetching)이 작동하여 성능이 극대화됩니다.
캐시 라인 (Cache Line)
대부분의 x86-64 시스템에서 캐시 라인은 64바이트입니다.
// 한 번의 메모리 접근으로 64바이트 전체가 캐시로 로드됨
alignas(64) int arr[16]; // 16 * 4 = 64바이트, 64바이트 정렬이므로 정확히 1 캐시 라인
arr[0] = 1; // 메인 메모리 접근 (캐시 미스)
// 이때 arr[0]부터 arr[15]까지 전부 캐시로 로드
arr[1] = 2; // 캐시 적중! (이미 로드됨)
arr[15] = 3; // 캐시 적중!vector는 원소가 연속되어 있어 캐시 라인 하나에 여러 원소가 함께 올라옵니다. list와 map은 노드가 따로 할당되므로 노드 하나에 접근할 때마다 새 캐시 라인이 필요하고, 노드가 메모리에 흩어져 있을수록 캐시 미스가 늘어납니다. 노드를 연속으로 할당한 직후라면 우연히 인접해 있을 수 있지만, 삽입과 삭제가 반복되면 이 인접성은 금방 사라집니다.
공간 지역성 (Spatial Locality)
// ✓ 좋음: 순차 접근 (공간 지역성 활용)
for (size_t i = 0; i < vec.size(); ++i) {
process(vec[i]); // 다음 요소가 이미 캐시에 있을 확률 높음
}
// ✗ 나쁨: 포인터 추적 (캐시 미스 다발)
for (const auto& x : lst) { // std::list
process(x); // 다음 노드 주소는 현재 노드를 읽어야 알 수 있음
}차이의 크기는 데이터 크기에 따라 달라집니다. 전체가 L1/L2 캐시에 들어가는 작은 데이터에서는 차이가 거의 없고, 캐시를 넘어서는 크기가 되면 순차 접근은 하드웨어 프리페처 덕분에 메모리 대역폭을 거의 다 쓰는 반면 흩어진 노드를 따라가는 접근은 원소마다 메모리 지연을 그대로 겪으므로 격차가 몇 배 이상으로 벌어집니다. 정확한 배율은 CPU와 원소 크기에 따라 다르므로, 결정이 중요한 코드라면 실제 데이터 크기로 직접 벤치마크해 보는 것이 맞습니다.
반복자 무효화 규칙
왜 중요한가?
무효화된 반복자를 사용하면 정의되지 않은 동작(UB)입니다. MSVC 디버그 빌드의 반복자 검사나 libstdc++의 _GLIBCXX_DEBUG, libc++의 하드닝 모드를 켜면 즉시 중단되지만, 일반 릴리스 빌드에서는 해제된 메모리를 조용히 읽어 재현하기 어려운 버그가 됩니다.
시퀀스 컨테이너 무효화 규칙
vector / string
std::vector<int> vec = {1, 2, 3, 4, 5};
// 1. push_back으로 인한 재할당
auto it = vec.begin();
vec.push_back(6); // capacity 초과 → 재할당
// ❌ it는 무효화됨! 사용하면 UB
// 2. insert로 인한 부분 무효화
vec.clear();
vec = {1, 2, 3, 4, 5};
it = vec.begin() + 2; // vec[2]를 가리킴
vec.insert(vec.begin() + 1, 99); // 중간 삽입
// ❌ it는 무효화됨! (삽입 지점 이후 모두 무효)
// 3. erase로 인한 부분 무효화
vec.clear();
vec = {1, 2, 3, 4, 5};
it = vec.begin() + 2;
vec.erase(vec.begin() + 1); // 중간 삭제
// ❌ it는 무효화됨! (삭제 지점 이후 모두 무효)안전한 패턴:
// ✓ erase는 다음 유효한 반복자를 반환함
for (auto it = vec.begin(); it != vec.end(); ) {
if (should_remove(*it)) {
it = vec.erase(it); // 반환값으로 갱신
} else {
++it;
}
}
// ✓ reserve로 재할당 방지
vec.reserve(1000);
for (int i = 0; i < 1000; ++i) {
vec.push_back(i); // 재할당 없음, 반복자 안전
}deque
std::deque<int> dq = {1, 2, 3, 4, 5};
// 양 끝 연산: 참조는 유효, 반복자는 무효화될 수 있음
auto& ref = dq[2];
dq.push_back(6); // ref는 여전히 유효
// 하지만 반복자는 무효화될 수 있음
// 중간 삽입/삭제: 모든 반복자 무효화
auto it = dq.begin();
dq.insert(dq.begin() + 2, 99);
// ❌ it 무효화!주의: deque는 “양 끝만 건드리면 안전”이라는 오해가 많습니다. 표준은 양 끝 연산에서도 반복자 무효화를 허용합니다.
list / forward_list
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
++it; // 두 번째 요소
lst.erase(it); // it만 무효화, 다른 반복자는 유효!
// ✓ 노드 기반이라 다른 노드의 반복자는 안전
auto it2 = lst.begin();
lst.push_back(6); // it2 여전히 유효list는 삽입·삭제가 다른 노드의 반복자에 영향을 주지 않는다는 것이 가장 큰 장점이고, 그 대가로 순회할 때 캐시 미스를 치릅니다.
연관 컨테이너 무효화 규칙
map / set (트리 기반)
std::map<int, std::string> m = {{1, "a"}, {2, "b"}, {3, "c"}};
auto it = m.find(2);
m.insert({4, "d"}); // ✓ it 여전히 유효!
m.erase(1); // ✓ it 여전히 유효!
m.erase(it); // ❌ it만 무효화, 다른 것들은 유효노드 기반이므로 삽입과 삭제가 다른 노드의 반복자에 영향을 주지 않습니다.
unordered_map / unordered_set (해시 테이블)
std::unordered_map<int, std::string> um = {{1, "a"}, {2, "b"}};
auto it = um.find(1);
// 재해시가 발생하지 않으면 it 유효
um.insert({3, "c"}); // load_factor() < max_load_factor()면 OK
// 재해시 발생 시 모든 반복자 무효화!
um.reserve(1000); // 재해시 발생
// ❌ it 무효화!삽입 후 원소 수가 max_load_factor() * bucket_count()를 넘게 되면 재해시(rehash)가 일어나 모든 반복자가 무효화됩니다. 다만 원소 노드 자체는 옮겨지지 않으므로, 원소를 가리키는 참조와 포인터는 재해시 뒤에도 유효합니다.
범위 기반 for의 함정
std::vector<int> vec = {1, 2, 3, 4, 5};
// ❌ 위험한 패턴
for (int x : vec) {
if (x % 2 == 0) {
vec.push_back(x * 10); // 재할당 → UB!
}
}
// ✓ 안전한 패턴 1: 인덱스 사용
size_t original_size = vec.size();
for (size_t i = 0; i < original_size; ++i) {
if (vec[i] % 2 == 0) {
vec.push_back(vec[i] * 10);
}
}
// ✓ 안전한 패턴 2: 별도 컨테이너
std::vector<int> to_add;
for (int x : vec) {
if (x % 2 == 0) {
to_add.push_back(x * 10);
}
}
vec.insert(vec.end(), to_add.begin(), to_add.end());컨테이너별 내부 구조
vector: 연속 메모리 배열
template<typename T>
class vector {
T* data_; // 데이터 배열 포인터
size_t size_; // 현재 요소 수
size_t capacity_; // 할당된 용량
};메모리 레이아웃:
[T0][T1][T2][T3][T4]... (연속된 힙 메모리)순차 접근이 가장 빠르고, 인덱스 접근이 O(1)이며, data() 포인터를 C API에 그대로 넘길 수 있습니다. 대신 중간 삽입·삭제는 뒤쪽 원소를 모두 옮겨야 해서 O(n)이고, 용량을 넘으면 전체를 새 버퍼로 옮기는 재할당이 일어납니다.
deque: 청크 배열
template<typename T>
class deque {
T** map_; // 청크 포인터 배열
size_t map_size_;
// 각 청크는 고정 크기 (libstdc++는 512바이트, MSVC는 16바이트 단위)
};메모리 레이아웃:
map_ → [chunk0*][chunk1*][chunk2*]...
↓ ↓ ↓
[T T T] [T T T] [T T T]양 끝 삽입·삭제가 O(1)이고, 인덱스 접근도 청크 번호와 오프셋 계산으로 O(1)입니다. 다만 접근마다 포인터를 한 번 더 거치고 청크 경계에서 연속성이 끊기므로 vector보다 캐시 효율이 낮습니다. 청크가 작은 MSVC 구현에서는 원소가 큰 경우 청크 하나에 원소가 하나만 들어가 사실상 노드 기반처럼 동작합니다.
list: 이중 연결 리스트
template<typename T>
class list {
struct Node {
T data;
Node* prev;
Node* next;
};
Node* head_;
Node* tail_;
size_t size_;
};메모리 레이아웃: 노드들이 힙 메모리에 흩어져 있음 (비연속)
위치를 이미 알고 있을 때의 삽입·삭제가 O(1)이고, 다른 노드의 반복자가 유지됩니다. splice로 노드를 복사 없이 다른 list로 옮길 수 있는 것도 list만의 기능입니다. 대신 원소마다 포인터 두 개와 할당 오버헤드가 붙고, 인덱스 접근은 O(n)이며, 순회할 때마다 포인터를 따라가야 합니다.
map: 레드-블랙 트리
template<typename Key, typename Value>
class map {
struct Node {
std::pair<Key, Value> data;
Node* parent;
Node* left;
Node* right;
Color color; // 레드-블랙 트리 색상
};
Node* root_;
size_t size_;
};주요 표준 라이브러리 구현은 map을 자가 균형 이진 탐색 트리인 레드-블랙 트리로 만듭니다. 키가 항상 정렬된 상태로 유지되므로 정렬 순회와 lower_bound/upper_bound 같은 범위 검색이 가능하고, 탐색·삽입·삭제가 최악에도 O(log n)입니다. 대신 노드마다 포인터 세 개와 색상 정보가 붙고, 탐색할 때 트리 깊이만큼 흩어진 노드를 따라가야 합니다.
unordered_map: 해시 테이블
// 개념 스케치: 실제 구현(libstdc++)은 모든 노드를 단일 연결 리스트로 잇고
// 버킷이 그 리스트의 위치를 가리키는 방식이다
template<typename Key, typename Value>
class unordered_map {
struct Node {
std::pair<Key, Value> data;
Node* next; // 체이닝용
};
std::vector<Node*> buckets_; // 버킷 배열
size_t size_;
float max_load_factor_; // 기본 1.0
};메모리 레이아웃:
buckets_ → [bucket0*][bucket1*][bucket2*]...
↓ ↓ ↓
[Node]→[Node] [Node] nullptr탐색·삽입·삭제가 평균 O(1)이라 원소가 많을수록 map보다 유리해지는 경향이 있습니다. 대신 해시가 한 버킷에 몰리면 최악 O(n)까지 떨어지고, 재해시 때마다 전체 원소를 다시 분배하는 비용이 들며, 순회 순서가 정해져 있지 않습니다.
vector 성장 전략과 최적화
성장 전략 (Growth Factor)
vector가 capacity를 초과하면 재할당이 발생합니다. 얼마나 늘릴까요?
표준은 성장 비율을 정하지 않고 push_back의 상환(amortized) O(1)만 요구합니다. libstdc++(GCC)와 libc++(Clang)는 2배, MSVC는 1.5배로 늘립니다.
std::vector<int> vec;
vec.reserve(10);
std::cout << vec.capacity() << '\n'; // 10
for (int i = 0; i < 11; ++i) {
vec.push_back(i);
std::cout << vec.capacity() << '\n';
}
// 출력 (GCC): 10, 10, ..., 20 (재할당 발생)reserve의 중요성
// ❌ 나쁨: 여러 번 재할당
std::vector<int> vec;
for (int i = 0; i < 1000; ++i) {
vec.push_back(i); // log2(1000) ≈ 10회 재할당
}
// ✓ 좋음: 한 번에 할당
std::vector<int> vec;
vec.reserve(1000);
for (int i = 0; i < 1000; ++i) {
vec.push_back(i); // 재할당 없음!
}reserve가 줄여 주는 것은 재할당 횟수와 그때마다 기존 원소를 옮기는 비용입니다. 1,000개 정도의 int라면 차이가 측정 오차 수준일 수 있고, 원소가 크거나(복사·이동 비용이 큼) 개수가 수백만 단위로 커질수록 차이가 벌어집니다. 효과를 확인하려면 같은 루프를 reserve 유무만 바꿔 여러 번 돌려 보는 것이 가장 확실합니다.
shrink_to_fit의 함정
std::vector<int> vec(1000000);
vec.clear(); // size는 0, capacity는 여전히 1000000
vec.shrink_to_fit(); // capacity를 size에 맞춤 (요청일 뿐, 강제 아님)shrink_to_fit()은 구속력 없는 요청이라 구현이 무시할 수 있고, 실제로 줄일 때는 새 버퍼를 할당해 원소를 옮기는 재할당 비용이 듭니다. 곧 다시 커질 벡터라면 줄였다가 또 늘리는 셈이므로, 메모리 프로파일링으로 필요가 확인된 경우에만 씁니다.
emplace_back vs push_back
struct Heavy {
std::string data;
Heavy(std::string s) : data(std::move(s)) {}
};
std::vector<Heavy> vec;
// push_back: 임시 객체 생성 → 이동
vec.push_back(Heavy("temp")); // 1. Heavy("temp") 생성
// 2. 이동 생성자 호출
// emplace_back: 제자리 생성 (더 효율적)
vec.emplace_back("temp"); // Heavy가 vector 내부에서 직접 생성생성자 인자로 새 객체를 만들 때는 emplace_back, 이미 있는 객체를 넣을 때는 push_back이 자연스럽습니다. 다만 emplace_back은 explicit 생성자도 호출하므로, std::vector<std::vector<int>> v; v.emplace_back(1000000);처럼 의도치 않은 변환이 컴파일 오류 없이 통과할 수 있다는 점은 알아 둘 필요가 있습니다.
unordered_map 최적화
로드 팩터 (Load Factor)
std::unordered_map<int, std::string> um;
std::cout << um.load_factor() << '\n'; // size() / bucket_count()
std::cout << um.max_load_factor() << '\n'; // 기본 1.0로드 팩터는 버킷당 평균 원소 수입니다. 낮게 잡으면 버킷 배열이 커져 메모리를 더 쓰는 대신 체인이 짧아지고, 높게 잡으면 메모리를 아끼는 대신 체인이 길어져 탐색 비용이 늘어납니다.
reserve와 rehash
std::unordered_map<int, std::string> um;
// ❌ 나쁨: 재해시 여러 번
for (int i = 0; i < 10000; ++i) {
um[i] = "value"; // 중간에 여러 번 재해시 발생
}
// ✓ 좋음: 미리 예약
std::unordered_map<int, std::string> um;
um.reserve(10000); // 재해시 없이 10000개 수용 가능
for (int i = 0; i < 10000; ++i) {
um[i] = "value";
}재해시는 모든 원소를 새 버킷 배열로 다시 분배하므로 O(n)입니다.
커스텀 해시 함수
사용자 정의 타입을 키로 쓰려면 해시 함수를 직접 제공해야 합니다. 여러 필드를 단순히 XOR하면 (1, 2)와 (2, 1)이 같은 값이 되므로, 아래처럼 필드를 섞어 주는 조합 함수를 씁니다.
struct Point {
int x, y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
// 커스텀 해시
struct PointHash {
size_t operator()(const Point& p) const {
// Boost hash_combine 스타일
size_t seed = 0;
seed ^= std::hash<int>{}(p.x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
std::unordered_map<Point, std::string, PointHash> map;보안: 해시 충돌 공격
공격자가 키를 고를 수 있으면 모든 키가 같은 버킷에 들어가도록 만들어 연산당 비용을 O(n)으로 떨어뜨릴 수 있습니다. libstdc++와 libc++의 정수용 std::hash는 값을 그대로 돌려주는 항등 함수이고 주요 구현 어디에도 시드 무작위화가 없으므로, 외부 입력을 키로 쓴다면 SipHash처럼 비밀 키를 받는 해시를 직접 지정하거나, 최악에도 O(log n)이 보장되는 map을 쓰는 것이 대응책입니다.
map vs unordered_map 선택 가이드
결정 트리
flowchart TD
A[컨테이너 선택] --> B{정렬이 필요한가?}
B -->|예| C[map 사용]
B -->|아니오| D{범위 쿼리가 필요한가?}
D -->|예| C
D -->|아니오| F{"외부 입력이 키가 되는가?<br/>(해시 충돌 공격 가능)"}
F -->|예| C
F -->|아니오| G[unordered_map 사용]
G --> H["개수를 알면 reserve"]
직접 측정할 때 확인할 것
두 컨테이너의 속도 차이는 키 타입, 원소 수, 해시 품질, 표준 라이브러리 구현, 할당자에 따라 크게 달라서 다른 환경에서 잰 배수를 그대로 가져오기 어렵습니다. 비교할 때는 다음을 지키면 결과를 믿을 수 있습니다.
- 실제 키 분포로 잰다: 연속된 정수 키는 해시가 거의 충돌하지 않고, map에서도 노드가 순서대로 할당되어 캐시에 유리합니다. 실제 서비스의 키(문자열 ID, 해시 값 등)로 재야 합니다.
- 삽입·탐색·순회를 따로 잰다: 한 번에 섞어 재면 어떤 연산이 병목인지 알 수 없습니다.
reserve유무를 나눠 잰다: unordered_map은 재해싱 비용이 삽입 시간에 크게 섞입니다.- 최적화된 빌드(-O2 이상)로, 여러 번 반복해 중앙값을 본다: 첫 실행은 페이지 폴트와 캐시 워밍업 영향이 큽니다.
일반적인 경향만 말하면, 키로 찾는 작업이 많을수록 unordered_map이 유리하고, 정렬 순회나 구간 검색이 필요하면 map 말고는 선택지가 없습니다. 둘 다 노드 기반이라 순회는 연속 메모리 컨테이너보다 느리므로, 순회가 가장 잦은 작업이라면 아래의 정렬된 vector(flat map)를 검토하는 편이 낫습니다.
메모리 사용량
메모리는 노드 크기로 어림할 수 있습니다. 64비트 libstdc++ 기준으로 std::map<int, int>의 노드는 색상과 포인터 세 개(32바이트)에 키·값 8바이트가 붙어 40바이트이고, 여기에 malloc의 청크 헤더와 정렬이 더해집니다. std::unordered_map<int, int>의 노드는 다음 포인터와 키·값으로 더 작지만, 원소 수만큼의 버킷 포인터 배열이 따로 붙습니다. 그래서 둘 다 원소당 수십 바이트를 쓰며, 데이터 자체가 8바이트인 std::vector<std::pair<int, int>>보다 몇 배 큽니다. 정확한 값은 할당자에 따라 달라지므로 실제 환경에서 RSS나 할당 추적 도구로 확인해야 합니다.
키 타입 요구 사항과 map만 할 수 있는 일
사용자 정의 구조체를 키로 쓸 때 요구 사항도 다릅니다. map은 operator<(또는 비교 함수 객체) 하나면 되지만, unordered_map은 해시 함수와 operator==가 모두 필요하고 해시를 잘못 조합하면 성능이 조용히 떨어집니다. 해시 함수를 작성하기 번거로운 복합 키라면 그 자체가 map을 고를 이유가 됩니다.
map을 고르는 가장 분명한 이유는 구간 검색입니다. lower_bound(≥)와 upper_bound(>)로 키 범위를 바로 잘라낼 수 있어 시계열 데이터나 이벤트 일정처럼 “특정 범위의 키”를 찾는 작업에 맞습니다.
std::map<int, std::string> events{{100, "A"}, {200, "B"}, {300, "C"}};
for (auto it = events.lower_bound(150); it != events.upper_bound(250); ++it) {
std::cout << it->first << ": " << it->second << '\n'; // 200: B
}순위표처럼 점수를 키로 정렬할 때는 키가 중복될 수 있다는 점을 놓치기 쉽습니다. std::map<int, std::string>에 같은 점수를 넣으면 이전 이름이 덮어써지므로, 이런 경우에는 std::multimap<int, std::string, std::greater<int>>처럼 중복 키를 허용하는 컨테이너를 씁니다.
실전 벤치마크
아래 코드는 직접 돌려 볼 수 있는 측정 뼈대입니다. 절대 시간은 CPU·할당자·컴파일러 옵션에 따라 크게 달라지므로, 주석에는 결과가 어느 쪽으로 나오는지와 그 이유만 적었습니다.
삽입 성능
// 벤치마크 코드
constexpr size_t N = 100000;
// vector (reserve 있음)
std::vector<int> vec;
vec.reserve(N);
auto start = std::chrono::steady_clock::now();
for (size_t i = 0; i < N; ++i) {
vec.push_back(i);
}
auto end = std::chrono::steady_clock::now();
// 할당 1번(reserve), 이후는 연속 메모리에 쓰기만 함
// list
std::list<int> lst;
start = std::chrono::steady_clock::now();
for (size_t i = 0; i < N; ++i) {
lst.push_back(i);
}
end = std::chrono::steady_clock::now();
// 원소마다 노드 할당 → vector보다 느림 (격차는 할당자 속도에 좌우)탐색 성능
// vector: 선형 탐색
auto it = std::find(vec.begin(), vec.end(), target);
// O(n), 하지만 캐시 친화적: 원소가 적으면 트리·해시보다 빠를 수도 있음
// map: 이진 탐색 트리
auto it = map.find(target);
// O(log n), 트리 깊이만큼 포인터 추적 (10만 개면 최소 17단계, 레드-블랙 트리는 최대 그 2배)
// unordered_map: 해시
auto it = um.find(target);
// O(1) 평균: 해시 계산 + 버킷 한 번 접근, 원소가 많을수록 유리순회 성능
// vector
for (int x : vec) { sum += x; }
// 연속 메모리: 프리페처와 벡터화 덕분에 가장 빠름
// list
for (int x : lst) { sum += x; }
// 노드마다 포인터 추적: 노드가 흩어져 있을수록 느려짐
// map
for (auto& [k, v] : map) { sum += v; }
// 트리 중위 순회: 부모·자식 포인터를 오가며 list보다도 느린 경우가 많음프로덕션 최적화 패턴
”vector를 먼저 고려하라”
// ❌ 습관적으로 list 사용
std::list<Item> items;
for (auto& item : source) {
items.push_back(process(item));
}
// ✓ 대부분의 경우 vector가 더 빠름
std::vector<Item> items;
items.reserve(source.size());
for (auto& item : source) {
items.push_back(process(item));
}특히 정렬 상태를 유지하며 삽입하는 경우, list도 삽입 위치를 찾는 데 O(n) 순회가 필요하므로 복잡도 이점이 사라집니다. 이때는 위치 탐색(vector는 이진 탐색도 가능)과 원소 이동 모두 연속 메모리에서 일어나는 vector가 대체로 유리합니다. 어느 크기까지 그런지는 원소 크기와 하드웨어에 따라 다르므로 측정으로 확인합니다.
순서가 중요하지 않은 vector라면 중간 삭제도 O(1)로 만들 수 있습니다. 지울 원소 자리에 마지막 원소를 옮기고 pop_back()하는 swap-and-pop입니다. 게임 엔티티처럼 자주 추가·삭제되지만 그보다 훨씬 자주 전체를 순회하는 데이터에 흔히 쓰고, 지울 원소가 마지막 원소일 때 자기 자신으로 이동 대입하지 않도록 검사해 둡니다.
if (it != std::prev(v.end())) {
*it = std::move(v.back());
}
v.pop_back();list가 제 역할을 하는 경우
list가 이기는 것은 위치를 이미 알고 있어서 탐색이 필요 없고, 다른 원소의 반복자가 유지되어야 할 때입니다. 대표적인 예가 LRU 캐시입니다. 해시맵이 리스트 노드의 반복자를 들고 있으므로 위치 탐색이 없고, splice로 노드를 재할당 없이 옮겨도 반복자가 그대로 유효합니다.
std::list<Entry> lru; // 앞쪽이 가장 오래된 항목
std::unordered_map<Key, std::list<Entry>::iterator> index;
auto it = index.at(key);
lru.splice(lru.end(), lru, it); // 최근 사용으로 이동: O(1), 반복자 유지
// 용량 초과 시
index.erase(lru.front().key);
lru.pop_front();정렬도 차이가 있습니다. list는 임의 접근 반복자가 없어 std::sort를 쓸 수 없고 멤버 sort()(병합 정렬)를 씁니다. 복잡도는 같지만 노드를 따라가는 정렬이라 vector + std::sort보다 보통 느리고, 대신 링크만 바꾸므로 기존 반복자가 유효하게 남습니다. deque는 고정 크기 청크를 여러 개 할당하므로, 원소가 매우 많아 하나의 큰 연속 블록을 잡기 부담스럽거나 재할당 중 이전·새 버퍼가 함께 존재하는 순간의 최대 메모리가 문제일 때 vector의 대안이 됩니다.
작은 컨테이너의 할당 횟수
std::vector<int> small_vec = {1, 2, 3}; // 힙 할당 1회
std::list<int> small_lst = {1, 2, 3}; // 노드마다 힙 할당, 총 3회원소가 몇 개 안 되는 컨테이너를 자주 만들고 버린다면 할당 횟수 자체가 비용의 대부분입니다. 이런 경우에는 일정 개수까지는 객체 안의 버퍼에 원소를 저장해 힙 할당을 아예 하지 않는 소형 벡터(boost::container::small_vector, LLVM의 SmallVector)가 쓰입니다.
flat_map 패턴
정렬된 vector로 map을 흉내 내는 패턴:
// Boost.Container의 flat_map, C++23 std::flat_map과 같은 아이디어
template<typename K, typename V>
class flat_map {
std::vector<std::pair<K, V>> data_;
public:
auto find(const K& key) {
auto it = std::lower_bound(data_.begin(), data_.end(), key,
[](const auto& p, const K& k) { return p.first < k; });
if (it != data_.end() && it->first == key)
return it;
return data_.end();
}
// 삽입 시 정렬 유지
};원소가 연속 메모리에 있어 순회가 map보다 훨씬 빠르고, 이진 탐색도 노드를 따라가지 않으므로 캐시 효율이 좋습니다. 대신 삽입·삭제가 O(n)이고 삽입하면 반복자가 무효화되므로, 한 번 만들어 두고 주로 읽는 설정 테이블이나 조회 테이블에 적합합니다. 대량으로 넣을 때는 하나씩 정렬 삽입하지 말고 전부 넣은 뒤 한 번 정렬하는 편이 빠릅니다. C++23부터는 표준 std::flat_map을 쓸 수 있습니다.
unordered_map 튜닝
std::unordered_map<Key, Value> um;
// 1. 미리 예약
um.reserve(expected_size);
// 2. 로드 팩터 조정 (선택적)
um.max_load_factor(0.75f); // 충돌 감소, 메모리 증가
// 3. 커스텀 해시 (필요 시)
std::unordered_map<Key, Value, CustomHash> um;
// 4. 재해시 모니터링
auto old_bucket_count = um.bucket_count();
// ... 삽입 ...
if (um.bucket_count() != old_bucket_count) {
// 재해시 발생! 성능 영향 확인
}메모리 풀 패턴
빈번한 할당/해제 시:
// 커스텀 할당자 사용
template<typename T>
class PoolAllocator {
// 메모리 풀 구현
};
std::vector<int, PoolAllocator<int>> vec;
std::list<int, PoolAllocator<int>> lst;노드 기반 컨테이너처럼 작은 할당이 잦을 때 풀 할당자는 할당 비용과 단편화를 줄이고, 노드를 인접한 메모리에 배치해 캐시 효율도 높일 수 있습니다. 한 번에 큰 블록을 잡는 vector에는 효과가 거의 없습니다. C++17의 std::pmr::monotonic_buffer_resource나 std::pmr::unsynchronized_pool_resource를 쓰면 할당자를 직접 만들지 않고도 같은 효과를 낼 수 있습니다.
측정으로 확인하기
컨테이너를 바꾸기 전에는 Linux의 perf(캐시 미스는 perf stat -e cache-misses), macOS의 Instruments, Intel VTune, Visual Studio 프로파일러로 실제 병목이 컨테이너 연산인지 먼저 확인합니다. 바꾼 뒤에도 같은 입력으로 다시 재서 개선을 확인해야 합니다.
컨테이너 선택 흐름
flowchart TD
Start[컨테이너 선택] --> Q1{크기가 컴파일 타임에 고정?}
Q1 -->|예| Array["std::array"]
Q1 -->|아니오| Q3{키로 찾는가?}
Q3 -->|아니오| Q4{앞쪽 삽입/삭제가 잦은가?}
Q4 -->|예| Deque["std::deque"]
Q4 -->|아니오| Q5{다른 원소의 반복자·주소 안정성이 필수?}
Q5 -->|예| List["std::list"]
Q5 -->|아니오| Vector["std::vector"]
Q3 -->|예| Q6{정렬 순회나 범위 검색이 필요?}
Q6 -->|예| Q8{수정이 드문가?}
Q8 -->|예| Flat["정렬된 vector / flat_map"]
Q8 -->|아니오| Map["std::map"]
Q6 -->|아니오| UMap["std::unordered_map + reserve"]
출발점은 vector이고, 다른 컨테이너는 vector로 해결되지 않는 구체적인 요구(정렬, 반복자 안정성, 앞쪽 삽입)가 있을 때 고릅니다.