C++ vector 성능: 캐시 친화성, 용량 성장 전략, reserve 최적화

핵심 개념: push_back이 반복될 때 비용은 용량(capacity)이 부족해 일어나는 재할당에서 나옵니다. 개수를 대략 알면 reserve(n) 한 줄로 재할당을 없앨 수 있습니다. vector<bool>은 비트 단위로 압축된 특수화라 일반 vector처럼 동작하지 않으므로, 원소 참조가 필요하면 vector<uint8_t> 등을 고려합니다.

들어가며: vector에 push_back만 했는데 왜 이렇게 느릴까?

파일에서 읽은 100만 개를 vector에 넣는 코드

CSV(Comma-Separated Values, 쉼표로 구분된 값) 파일을 파싱해서 vector에 저장하는 코드가 있습니다. 데이터가 많아지면 느려지는데, 이때 가장 먼저 의심하게 되는 것이 push_back마다 일어날 수 있는 재할당입니다.

문제의 코드에서 std::vector<int> data는 빈 벡터로 시작하므로 초기 capacity(내부 버퍼 크기)는 0입니다. while (file >> value)로 파일에서 정수를 하나씩 읽어 올 때마다 push_back(value)를 호출하는데, 벡터가 꽉 찰 때마다 표준 라이브러리 구현은 “더 큰 메모리를 새로 할당 → 기존 원소를 옮김 → 이전 메모리 해제”를 반복합니다. 데이터가 100만 개라면 이 재할당이 약 20번 일어나고, 그때마다 그 시점까지의 원소를 전부 옮깁니다.

문제의 코드:

std::vector<int> loadData(const std::string& filename) {
    std::vector<int> data;  // 초기 capacity = 0
    
    std::ifstream file(filename);
    int value;
    while (file >> value) {
        data.push_back(value);  // 재할당이 반복됨!
    }
    
    return data;
}

빈 vector는 초기 capacity가 0이라, push_back이 반복될 때마다 용량이 부족하면 재할당(더 큰 버퍼 할당 → 기존 원소 복사/이동 → 이전 버퍼 해제)이 발생합니다. 100만 개를 넣으면 재할당이 약 20번 정도 일어나며, 매번 기존 원소 전체를 옮기므로 시간이 크게 늘어납니다.

원인:

• vector는 용량이 부족하면 메모리를 재할당 비유하면 vector는 STL(Standard Template Library, 표준 템플릿 라이브러리—C++ 표준이 제공하는 컨테이너·반복자·알고리즘 모음)의 “연속된 칸이 있는 서랍”인데, 칸이 꽉 차면 “더 큰 서랍으로 이사”합니다. 이사할 때마다 기존 물건을 전부 새 서랍으로 옮겨야 하므로, 이사 횟수가 많으면 느려집니다.
• 재할당 시 기존 데이터를 새 메모리로 복사
• 100만 개 데이터면 재할당이 약 20번 발생

개수가 미리 대략 정해져 있으면 reserve()로 한 번에 공간을 잡아 두면 재할당과 복사를 줄일 수 있습니다. size()와 capacity()의 차이를 알아 두면, “왜 지금 느린지”를 로그만으로도 추정할 때 도움이 됩니다.

vector가 커지는 방식: 대부분의 구현에서는 capacity가 부족해지면 기존 capacity의 약 2배로 재할당합니다. 따라서 원소를 계속 push_back하면 재할당 횟수가 로그에 비례해 늘어나고, 100만 개처럼 많을 때는 reserve 없이 하면 20번 안팎의 재할당이 일어날 수 있습니다. 한 번 재할당할 때마다 기존 원소 전체를 새 버퍼로 복사(또는 이동)하므로, reserve로 재할당 횟수를 줄이는 것이 성능에 큰 영향을 줍니다.

실무 팁: 정확한 개수를 모르면 “대략 최대치”만 예상해도 reserve(예상_개수)를 호출해 두면 재할당 횟수가 크게 줄어듭니다. 너무 크게 잡으면 메모리만 많이 쓰므로, 로그나 프로파일로 한 번 확인해 보는 것이 좋습니다.

해결 후에서는 data.reserve(1000000)으로 “최대 100만 개까지 넣을 공간”을 한 번에 미리 잡아 둡니다. 그러면 push_back을 반복해도 내부 버퍼가 부족해지지 않아 재할당이 일어나지 않으며, 기존 원소를 복사하는 비용이 사라집니다. 나머지 로직(파일 열기, 값 읽기, push_back)은 동일합니다.

해결 후:

std::vector<int> loadData(const std::string& filename) {
    std::vector<int> data;
    data.reserve(1000000);  // 미리 공간 확보
    
    std::ifstream file(filename);
    int value;
    while (file >> value) {
        data.push_back(value);  // 재할당 없음!
    }
    
    return data;
}

reserve(1000000)으로 “최대 100만 개” 공간을 한 번에 잡아 두므로, 그 안에서 push_back을 해도 재할당이 일어나지 않습니다. 기존 원소를 옮기는 비용이 없어져 대량 삽입 시 훨씬 빨라지고, 실행 시간이 10초에서 0.5초 수준으로 줄어드는 효과를 얻을 수 있습니다.

결과: 재할당 횟수가 약 20번에서 0번으로 줄고, 재할당 순간 옛 버퍼와 새 버퍼가 함께 살아 있어 생기던 메모리 피크도 사라집니다. 다만 이 예제처럼 int를 파일에서 읽는 경우, 재할당으로 옮기는 데이터는 모두 합쳐도 최종 크기의 두 배 정도(수 MB)라서 시간 대부분은 스트림 파싱이 차지합니다. reserve만으로 전체가 몇 배씩 빨라지지는 않는다는 뜻입니다. 효과가 크게 드러나는 것은 원소가 크거나 이동 비용이 비쌀 때, 그리고 입력 파싱 없이 메모리 안에서만 대량으로 쌓을 때입니다. 실제로 어디가 느린지는 아래 벤치마크 코드처럼 나눠 재 보는 것이 가장 확실합니다.

로그 수집, 게임 엔티티, 패킷 버퍼에서의 재할당 병목

실무에서 자주 겪는 재할당 성능 문제: 로그 수집(초당 1만 건), 게임 엔티티(60fps×100개), 패킷 버퍼 등에서 reserve 없이 push_back을 반복하면 재할당이 병목이 됩니다. 100만 개 기준 20회 재할당 × 평균 50만 개 복사 ≈ 10억 번 원소 이동. 핵심: “개수를 대략이라도 알면 reserve”가 가장 효과적입니다.

이 글을 읽으면:

• vector와 string의 내부 동작을 이해할 수 있습니다.
• capacity와 size의 차이를 알 수 있습니다.
• 메모리 재할당을 최소화하는 방법을 익힐 수 있습니다.
• 실전에서 성능을 최적화할 수 있습니다.

이 글의 범위

std::vector의 초기화 방법(v(5)와 v{5}의 차이), 추가·삭제·접근 연산, 반복자 사용법 같은 기본은 #13-1 std::vector 제대로 쓰기에서 다룹니다. 이 글은 그 기본을 안다고 보고, 왜 vector가 빠르거나 느려지는지(size와 capacity, 재할당, 캐시 지역성)와 std::string의 SSO처럼 성능에 직접 영향을 주는 부분에 집중합니다.

---

size와 capacity는 다르다

size: 실제 원소 개수

size()는 현재 들어 있는 원소의 개수입니다. []로 접근할 수 있는 유효한 인덱스는 0부터 size()-1까지입니다.

std::vector<int> vec = {1, 2, 3};
std::cout << vec.size() << "\n";  // 3

size()는 현재 들어 있는 원소 개수이며, 유효한 인덱스는 0부터 size()-1까지입니다. []로 접근할 때 이 범위를 벗어나면 미정의 동작이 되므로, 필요하면 at()으로 범위 검사가 있는 접근을 쓸 수 있습니다.

capacity: 할당된 메모리 크기

capacity()는 재할당 없이 담을 수 있는 최대 원소 개수입니다. size는 push_back할 때마다 1씩 늘지만, capacity는 부족해질 때만 (보통 2배로) 늘어납니다. 아래처럼 하나씩 넣어 보면, 세 번째 push_back 시점에 capacity가 2에서 4로 바뀌는 것을 확인할 수 있습니다.

std::vector<int> vec;
std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << "\n";
// size: 0, capacity: 0

vec.push_back(1);
std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << "\n";
// size: 1, capacity: 1

vec.push_back(2);
std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << "\n";
// size: 2, capacity: 2

vec.push_back(3);
std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << "\n";
// size: 3, capacity: 4 (재할당 발생!)

capacity()는 재할당 없이 담을 수 있는 최대 원소 개수입니다. push_back을 할 때마다 size는 1씩 늘고, capacity가 부족해지면 대부분 구현에서 2배로 늘리며 재할당이 일어납니다. 위 예에서는 세 번째 push_back 시 capacity가 2에서 4로 바뀝니다.

재할당 전략:

• 대부분의 구현에서 capacity가 부족하면 2배로 증가
• 예: 0 → 1 → 2 → 4 → 8 → 16 → 32 …

size vs capacity 시각화

flowchart LR
    subgraph vec["vector (size=3, capacity=4)"]
        direction TB
        V0["[0] 10"]
        V1["[1] 20"]
        V2["[2] 30"]
        V3["[3] (빈 공간)"]
        V0 --> V1 --> V2 --> V3
    end
    size["size() = 3br/유효한 원소 개수"]
    cap["capacity() = 4br/재할당 없이 담을 수 있는 최대 개수"]

위 다이어그램 설명: size는 실제로 들어 있는 원소 개수(3개)이고, capacity는 현재 할당된 버퍼가 담을 수 있는 최대 개수(4개)입니다. size가 capacity에 도달하면 다음 push_back 시 재할당이 발생합니다.

reserve vs capacity 성장 다이어그램

reserve 없이 push_back 시 capacity 변화:

flowchart LR
    subgraph growth[capacity 2배 성장]
        G0[0] --> G1[1]
        G1 --> G2[2]
        G2 --> G3[4]
        G3 --> G4[8]
        G4 --> G5[16]
        G5 --> G6[32]
        G6 --> G7[...]
    end

위 다이어그램 설명: reserve 없이 push_back을 반복하면 capacity가 0→1→2→4→8→16→32…처럼 2배씩 증가합니다. 각 화살표 시점에 재할당이 발생합니다.

reserve 사용 시: reserve(100) 후 push_back 100회 → 재할당 0회. reserve 없이는 5개 넣을 때까지 3번 재할당(0→1→2→4→8)이 발생합니다.

---

연속 메모리와 캐시 지역성: vector가 list보다 빠른 이유

캐시 지역성과 연속 메모리

vector의 가장 큰 성능 이점은 연속 메모리 배치입니다. 현대 CPU는 메모리를 64바이트 캐시 라인 단위로 가져오므로, vector의 한 원소에 접근하면 다음 15개 정수(int 기준)를 자동으로 캐시에 미리 로드합니다. 반면 list는 노드가 힙에 흩어져 있어 매 접근마다 캐시 미스 (~100ns 패널티)가 발생합니다.

직접 재 보기: 아래 코드는 같은 개수의 정수를 vector, list, deque에 넣고 순회 시간을 잽니다. 절대 수치는 CPU와 원소 수에 따라 크게 달라지지만, 결과의 순서는 거의 항상 vector가 가장 빠르고 list가 가장 느리며, 원소 수가 CPU 캐시 크기를 넘어설수록 차이가 커집니다.

• vector: 원소가 연속 메모리에 있어 64바이트 캐시 라인 하나에 int 16개가 함께 올라오고, 하드웨어 프리페처가 다음 캐시 라인을 미리 가져옵니다.
• deque: 고정 크기 블록 안에서는 연속이라 vector와 비슷하게 동작하지만, 블록 경계마다 한 번씩 다른 메모리로 건너갑니다.
• list: 노드가 따로 할당되어 다음 노드 주소를 읽기 전에는 어디로 갈지 알 수 없으므로, 노드가 메모리에 흩어져 있으면 거의 매 원소마다 캐시 미스가 날 수 있습니다. 노드를 방금 순서대로 할당했다면 할당자가 가까운 주소에 놓아 주어 실험에서는 차이가 예상보다 작게 나올 수 있고, 삽입·삭제를 오래 반복한 실제 프로그램에서는 더 벌어집니다.

// 순회 시간 비교 (g++ -O3 -std=c++23)
#include <vector>
#include <list>
#include <chrono>
#include <iostream>

template<typename Container>
void benchmark(const std::string& name) {
    Container c(100'000, 42);
    
    auto start = std::chrono::high_resolution_clock::now();
    int sum = 0;
    for (const auto& val : c) {
        sum += val;  // 캐시 지역성 테스트
    }
    auto end = std::chrono::high_resolution_clock::now();
    
    std::chrono::duration<double, std::milli> elapsed = end - start;
    std::cout << name << ": " << elapsed.count() << "ms (sum=" << sum << ")\n";
}

int main() {
    benchmark<std::vector<int>>("vector");  // 연속 메모리: 가장 빠름
    benchmark<std::list<int>>("list");      // 노드마다 포인터 추적: 몇 배 이상 느린 것이 보통
}

push_back이 내부에서 하는 일

push_back 한 번은 내부적으로 다음 네 단계로 이루어집니다:

1. 지수 성장 전략 (2× 증가): 재할당 횟수를 log(n)으로 유지 → n개 삽입 시 총 비용 O(n), 개별 push_back amortized O(1)
2. 성장 인자 재사용: 이전 버퍼 크기 정보 재활용 → 재할당 패턴 예측 가능
3. 캐시 친화적 복사: 연속 메모리 → CPU 프리페처 활성화 → 복사 속도 향상
4. 이동 의미론 최적화: C++11+ 이동 생성자 사용 → 복사 대신 포인터 이동 (string, vector 같은 복잡한 타입에서 큰 차이)

실무 권장:

// 1. 개수를 대략이라도 아는 경우 → reserve (최고 우선순위)
vec.reserve(예상_크기);  // 재할당 0회, 가장 빠름

// 2. 개수 모르지만 소량 (< 1000) → 그냥 push_back
// 재할당 10회 미만, 미세 최적화보다 코드 간결성

// 3. 대량 + 개수 모름 → 청크 단위 reserve
vec.reserve(1000);  // 초기 버퍼
// ...필요시 vec.reserve(vec.size() * 2);  // 동적 확장

// 4. 성능 중요 + 반복 패턴 → 프로파일 후 최적값 결정
// perf stat으로 L1 cache miss 측정, 최적 reserve 크기 찾기

---

reserve와 shrink_to_fit으로 재할당 줄이기

reserve: 미리 공간 확보

원소 개수를 대략 알고 있으면 reserve(n)으로 미리 n개만큼 공간을 잡아 두면 됩니다. 그러면 그 안에서 push_back을 할 때 재할당이 일어나지 않아서, 대량 삽입 시 훨씬 빠르고 메모리 단편화도 줄어듭니다. reserve는 size를 바꾸지 않고 capacity만 늘립니다.

std::vector<int> vec;
vec.reserve(1000);  // 1000개 공간 미리 확보

for (int i = 0; i < 1000; ++i) {
    vec.push_back(i);  // 재할당 없음
}

std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << "\n";
// size: 1000, capacity: 1000

reserve(1000)은 size는 그대로 두고 capacity만 최소 1000이 되게 합니다. 그 다음 1000번 push_back해도 재할당이 없어 대량 삽입이 빠르고, 메모리 단편화도 줄어듭니다. 개수를 대략이라도 알면 reserve를 호출하는 것이 좋습니다.

shrink_to_fit: 불필요한 메모리 해제

resize(n)으로 size를 줄여도 capacity는 그대로라서, 메모리를 많이 쓰는 상태가 유지될 수 있습니다. shrink_to_fit()은 “지금 size에 맞게 capacity를 줄여도 된다”고 구현에 요청하는 것이며, 구현이 반드시 줄인다는 보장은 없지만 대부분 줄여 줍니다. 메모리를 아껴야 할 때 사용합니다.

std::vector<int> vec(1000);
vec.resize(10);  // size는 10, capacity는 1000

std::cout << "Before: capacity = " << vec.capacity() << "\n";  // 1000

vec.shrink_to_fit();  // 불필요한 메모리 해제

std::cout << "After: capacity = " << vec.capacity() << "\n";  // 10

resize(10)으로 size를 줄여도 capacity는 그대로라서, 1000개치 메모리가 남을 수 있습니다. shrink_to_fit()은 “지금 size에 맞게 capacity를 줄여도 된다”고 요청하는 것이며, 구현이 따라줄 경우 불필요한 메모리를 줄일 수 있습니다. 반드시 줄어든다는 보장은 없습니다.

재할당 비용 측정

같은 개수만큼 push_back할 때, reserve 없이 하면 재할당이 여러 번 일어나고, reserve를 한 번 해 두면 재할당이 없어서 시간 차이가 큽니다. 아래 코드는 각각 100만 개 삽입에 걸리는 시간을 재서, reserve 사용 시 얼마나 빨라지는지 확인하는 예입니다.

#include <chrono>

void testWithoutReserve() {
    auto start = std::chrono::high_resolution_clock::now();
    
    std::vector<int> vec;
    for (int i = 0; i < 1000000; ++i) {
        vec.push_back(i);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "Without reserve: " << duration.count() << " ms\n";
}

void testWithReserve() {
    auto start = std::chrono::high_resolution_clock::now();
    
    std::vector<int> vec;
    vec.reserve(1000000);
    for (int i = 0; i < 1000000; ++i) {
        vec.push_back(i);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "With reserve: " << duration.count() << " ms\n";
}

int main() {
    testWithoutReserve();
    testWithReserve();     // 보통 이쪽이 더 빠름
}

reserve 없이 100만 번 push_back하면 재할당이 약 20번 일어나고, 그때마다 기존 원소를 새 버퍼로 옮깁니다. reserve(1000000) 후에는 할당이 한 번뿐입니다. 다만 2배씩 늘어나는 동안 옮기는 총량은 최종 크기의 두 배 정도라서, int처럼 옮기기 싼 타입에서는 차이가 생각보다 작을 수 있습니다. 원소가 크거나 복사 비용이 클수록, 그리고 재할당 때 반복자·포인터가 무효화되는 문제를 피해야 할수록 reserve의 가치가 커집니다.

Vector 최적화 완전 예제

실무에서 자주 쓰는 최적화 기법을 모두 적용한 예제입니다.

예제 1: 대량 데이터 로드 (reserve + emplace_back + 이동)

#include <vector>
#include <string>
#include <fstream>
#include <sstream>

struct Record {
    int id;
    std::string name;
    double value;
    Record(int i, std::string n, double v) : id(i), name(std::move(n)), value(v) {}
};

// ✅ 최적화 적용: reserve + emplace_back + 이동
std::vector<Record> loadRecords(const std::string& filename) {
    std::vector<Record> records;
    records.reserve(100000);  // 1. 개수 예상해 reserve

    std::ifstream file(filename);
    std::string line;
    while (std::getline(file, line)) {
        std::istringstream iss(line);
        int id;
        std::string name;
        double value;
        if (iss >> id >> name >> value) {
            // 2. emplace_back: 임시 객체 없이 직접 생성
            records.emplace_back(id, std::move(name), value);
        }
    }
    return records;  // 3. RVO로 이동 반환
}

reserve로 재할당을 막으며, emplace_back으로 복사/이동을 줄이며, std::move(name)으로 string 복사를 피합니다. 반환 시 RVO(Return Value Optimization)로 이동이 발생합니다.

예제 2: 조건부 필터링

std::vector<int> result;
result.reserve(input.size());
std::copy_if(input.begin(), input.end(), std::back_inserter(result),
              { return x % 2 == 0; });
result.shrink_to_fit();  // 선택

reserve로 재할당을 막으며, copy_if로 O(n) 필터링합니다.

예제 3: 중복 제거

std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
vec.shrink_to_fit();  // 선택

sort + unique + erase는 O(n log n)이며, set보다 캐시 친화적입니다.

---

std::string과 SSO(Small String Optimization)

string도 vector와 비슷

std::string은 std::vector<char>와 비슷하게 동작합니다:

• 동적 메모리 할당
• capacity와 size 개념
• 재할당 발생

string도 size/capacity를 가지므로, 빈 문자열은 보통 작은 capacity(SSO(Small String Optimization, 작은 문자열 최적화) 구간)를 가지고, 길이가 늘어나면 힙에 버퍼를 할당합니다. 구현에 따라 짧은 문자열은 객체 안에 그대로 들어가서 힙 할당이 0번일 수 있습니다.

std::string str;
std::cout << "size: " << str.size() << ", capacity: " << str.capacity() << "\n";
// size: 0, capacity: 15 (SSO: Small String Optimization)

str = "Hello, World! This is a long string.";
std::cout << "size: " << str.size() << ", capacity: " << str.capacity() << "\n";
// size: 38, capacity: 38 이상

string도 size()와 capacity()를 가지며, 빈 문자열은 구현에 따라 작은 capacity(SSO 구간)를 가질 수 있습니다. 짧은 문자열은 객체 안에 그대로 들어가 힙 할당이 없으며, 길이가 늘면 힙에 버퍼를 할당해 vector와 비슷하게 동작합니다.

SSO (Small String Optimization)

짧은 문자열은 힙 할당 없이 객체 내부에 저장:

std::string short_str = "Hi";  // 힙 할당 없음 (SSO)
std::string long_str = "This is a very long string that exceeds SSO limit";  // 힙 할당

SSO(Small String Optimization)로 짧은 문자열은 객체 내부 버퍼에 저장되어 힙 할당이 일어나지 않습니다. 일정 길이(보통 15~23바이트)를 넘으면 힙에 할당됩니다. 구현마다 한계가 다르지만, 짧은 문자열이 많을 때 할당 비용을 줄이는 최적화입니다.

SSO 한계: 보통 15~23바이트 (구현마다 다름)

SSO 동작 방식

flowchart LR
    subgraph sso["짧은 문자열 (SSO)"]
        S1["string 객체"]
        S2["객체 내부 버퍼br/'Hi' 저장"]
        S1 --> S2
    end
    subgraph heap["긴 문자열 (힙 할당)"]
        H1["string 객체"]
        H2[포인터]
        H3["힙 메모리br/'Very long string...'"]
        H1 --> H2 --> H3
    end

위 다이어그램 설명: 짧은 문자열(보통 15~23바이트 이하)은 string 객체 내부에 그대로 저장되어 힙 할당이 없습니다. 길이가 한계를 넘으면 포인터로 힙 메모리를 가리키며, vector와 비슷하게 동작합니다.

string 연산

+=와 append는 끝에 문자열을 붙이며, insert(위치, 문자열)은 지정한 인덱스에 삽입합니다. erase(시작, 길이)는 해당 구간을 지우고, substr(시작, 길이)는 부분 문자열을 복사해 반환합니다. find는 부분 문자열이나 문자가 나오는 첫 위치를 반환하며, 없으면 std::string::npos를 반환하므로 비교해서 사용해야 합니다.

std::string str = "Hello";

// 추가
str += " World";             // "Hello World"
str.append("!");             // "Hello World!"
str.push_back('?');          // "Hello World!?"

// 삽입
str.insert(5, ",");          // "Hello, World!?"

// 삭제
str.erase(5, 1);             // "Hello World!?" (쉼표 제거)
str.pop_back();              // "Hello World!" (? 제거)

// 부분 문자열
std::string sub = str.substr(0, 5);  // "Hello"

// 찾기
size_t pos = str.find("World");      // 6
if (pos != std::string::npos) {
    std::cout << "Found at: " << pos << "\n";
}

// 비교
if (str == "Hello World!") {
    std::cout << "Equal\n";
}

+=와 append는 끝에 붙이며, insert(위치, 문자열)는 지정 인덱스에 삽입합니다. erase(시작, 길이)는 그 구간을 지우고, substr은 부분 문자열을 새 string으로 복사해 반환합니다. find는 부분 문자열/문자의 첫 위치를 돌려주며, 없으면 npos를 반환하므로 비교해서 사용해야 합니다.

string 최적화

나쁜 예: 반복 연결

문자열에 +=로 반복해서 붙이면, 길이가 늘어날 때마다 재할당과 복사가 반복되어 비효율적입니다. 루프 안에서 수천 번 연결하면 시간이 눈에 띄게 늘어납니다.

std::string result;
for (int i = 0; i < 10000; ++i) {
    result += std::to_string(i) + ",";  // 재할당 반복
}

루프 안에서 +=로 계속 붙이면 길이가 늘어날 때마다 재할당과 복사가 반복됩니다. 1만 번 연결하면 재할당도 여러 번 일어나 시간이 많이 걸리므로, 대량 연결 시에는 reserve나 다른 방식(예: ostringstream)을 쓰는 것이 좋습니다.

좋은 예: reserve 사용

대략 필요한 길이를 알면 reserve로 한 번에 버퍼를 잡아 두면, 반복 연결 시 재할당 횟수가 줄어듭니다. 정확한 길이를 모르더라도 여유 있게 잡아 두면 효과가 있습니다.

std::string result;
result.reserve(100000);  // 미리 공간 확보
for (int i = 0; i < 10000; ++i) {
    result += std::to_string(i) + ",";
}

result.reserve(100000)으로 미리 공간을 잡아 두면, 루프 안에서 +=를 반복해도 재할당 횟수가 줄어듭니다. 정확한 최종 길이를 모르더라도 여유 있게 reserve해 두면 재할당으로 인한 비용을 크게 줄일 수 있습니다.

더 나은 예: stringstream

많은 조각을 한 번에 이어 붙일 때는 std::ostringstream을 쓰는 편이 낫습니다. 스트림이 내부 버퍼를 관리하며, 마지막에 str()로 한 번에 string을 꺼내면 재할당이 string에서 반복되는 것보다 효율적일 수 있습니다.

#include <sstream>

std::ostringstream oss;
for (int i = 0; i < 10000; ++i) {
    oss << i << ",";
}
std::string result = oss.str();

ostringstream에 <<로 여러 조각을 넣으면 스트림이 내부 버퍼를 관리하며, 마지막에 str()로 한 번에 string을 꺼냅니다. string에 +=를 반복하는 것보다 재할당이 적게 일어나거나 한 번에 처리될 수 있어, 많은 조각을 이어 붙일 때 유리합니다.

---

emplace_back, erase-remove, vector 회피

팁 1: emplace_back vs push_back

push_back(Point(1, 2))는 임시 Point를 만든 뒤 vector 안으로 복사 또는 이동합니다. emplace_back(1, 2)는 vector가 내부에서 생성자 인자만 받아서 그 자리에 직접 객체를 만들므로, 임시 생성과 한 번의 이동이 없어집니다. 복사/이동 비용이 있는 타입일수록 emplace_back이 유리합니다.

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {
        std::cout << "Constructor\n";
    }
};

std::vector<Point> vec;

// push_back: 임시 객체 생성 후 복사/이동
vec.push_back(Point(1, 2));
// Constructor (임시 객체)
// Move constructor (vector로 이동)

// emplace_back: 직접 생성
vec.emplace_back(1, 2);
// Constructor (vector 내부에서 직접 생성)

push_back(Point(1,2))는 임시 Point를 만든 뒤 vector로 복사 또는 이동하므로, 생성자와 이동 생성자가 호출됩니다. emplace_back(1, 2)는 vector 내부에서 생성자 인자만 받아 직접 객체를 만들므로 임시가 없으며, 복사/이동 비용이 있는 타입일수록 emplace_back이 유리합니다.

팁 2: 범위 기반 for에서 참조 사용

for (std::string str : vec)처럼 값으로 받으면 원소마다 복사가 일어납니다. string처럼 복사 비용이 있는 타입이면 불필요한 할당이 반복되므로, 읽기만 할 때는 const std::string&(또는 const auto&)로 참조해서 복사를 피하는 것이 좋습니다.

std::vector<std::string> vec = {"apple", "banana", "cherry"};

// ❌ 나쁜 예: 복사 발생
for (std::string str : vec) {
    std::cout << str << "\n";
}

// ✅ 좋은 예: 참조 사용
for (const std::string& str : vec) {
    std::cout << str << "\n";
}

for (std::string str : vec)처럼 값으로 받으면 매 반복마다 원소가 복사됩니다. string처럼 복사 비용이 큰 타입이면 불필요한 할당이 반복되므로, 읽기만 할 때는 const 참조(const std::string& 또는 const auto&)로 받아 복사를 피하는 것이 좋습니다.

팁 3: erase-remove idiom

루프 안에서 erase를 반복하면, 매번 뒤 원소들이 앞으로 당겨지고 반복자도 갱신해야 해서 O(n²)에 가깝습니다. std::remove는 “지울 값이 아닌 것”만 앞으로 모은 뒤 새 논리적 끝 반복자를 반환하며, 그 구간을 한 번에 erase하면 O(n)으로 같은 결과를 낼 수 있습니다. 이 조합을 erase-remove idiom이라고 부릅니다.

std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

// ❌ 나쁜 예: 루프에서 erase (O(n²))
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == 2) {
        it = vec.erase(it);
    } else {
        ++it;
    }
}

// ✅ 좋은 예: erase-remove (O(n))
vec.erase(std::remove(vec.begin(), vec.end(), 2), vec.end());

루프에서 매번 erase를 하면 그 뒤 원소들이 앞으로 당겨지고 반복자도 갱신해야 해서 O(n²)에 가깝습니다. remove는 “지울 값이 아닌 것”만 앞으로 모은 뒤 새 논리적 끝 반복자를 반환하며, erase(그 반복자, end())로 한 번에 지우면 O(n)으로 같은 결과를 낼 수 있습니다.

팁 4: data()로 C API 연동

C API가 T* 또는 const T*를 요구할 때는 vec.data()를 사용합니다. vector는 연속 메모리이므로 data()가 유효한 포인터를 반환하며, size()와 함께 data(), data() + size()로 범위를 넘길 수 있습니다.

// C API 호출 예
void process_array(const int* arr, size_t len);

std::vector<int> vec = {1, 2, 3, 4, 5};
process_array(vec.data(), vec.size());  // C API에 직접 전달

주의: push_back/insert/erase 등으로 vector가 수정되면 data()가 반환한 포인터가 무효화될 수 있습니다. C API 호출 중에는 vector를 수정하지 않도록 합니다.

팁 5: vector은 피하기

std::vector<bool>은 공간 절약을 위해 비트 단위로 압축되어 있어서, operator[]가 bool 참조가 아니라 프록시 객체를 반환합니다. 따라서 bool&를 기대하는 코드나 주소를 넘기는 API와 맞지 않을 수 있어, 일반적인 bool 시퀀스가 필요하면 std::vector<char>나 std::vector<uint8_t>를 쓰는 편이 안전합니다.

// ❌ vector<bool>은 특수화되어 있음 (비트 압축)
std::vector<bool> flags = {true, false, true};
// bool&를 반환하지 않음 (프록시 객체 반환)

// ✅ 대안: vector<char> 또는 vector<uint8_t>
std::vector<char> flags = {1, 0, 1};

vector<bool>은 비트로 압축되어 operator[]가 bool이 아니라 프록시를 반환합니다. bool&를 요구하는 코드나 주소를 넘기는 API와 맞지 않을 수 있어, 일반적인 bool 시퀀스가 필요하면 vector<char>나 vector<uint8_t>를 쓰는 편이 안전합니다.

---

npos 비교 누락과 string_view 수명 문제

vector subscript out of range, erase 루프에서의 반복자 무효화, reserve 후 인덱스 접근, data() 포인터 무효화처럼 vector를 쓰다 흔히 만나는 에러는 #13-1의 에러 절에 재현 코드와 함께 정리했습니다. 여기서는 문자열 쪽에서 자주 생기는 두 가지만 봅니다.

문제 1: string::find 결과를 npos와 비교하지 않음

원인: find()가 찾지 못하면 std::string::npos(size_t의 최댓값)를 반환합니다. 이 값을 그대로 substr의 시작 위치로 넘기면 std::out_of_range 예외가 나고, 직접 인덱스로 쓰면 범위를 벗어난 접근이 됩니다.

해결법:

// ❌ 나쁜 예: npos 검사 없음
std::string str = "Hello";
size_t pos = str.find("World");
std::string sub = str.substr(pos, 5);  // pos == npos → std::out_of_range

// ✅ 좋은 예: npos 검사
size_t pos = str.find("World");
if (pos != std::string::npos) {
    std::string sub = str.substr(pos, 5);
} else {
    std::cout << "Not found\n";
}

pos를 int에 담으면 npos가 -1로 바뀌어 비교가 우연히 맞는 것처럼 보이다가, 다른 곳에서 부호 없는 값과 섞이며 깨집니다. find의 결과는 항상 size_t(또는 auto)로 받는 것이 안전합니다.

문제 2: std::string_view가 임시 string을 가리킴

원인: string_view는 문자열을 소유하지 않고 포인터와 길이만 들고 있습니다. 함수가 반환한 임시 std::string으로 string_view를 만들면, 그 문장이 끝나는 순간 임시 객체가 사라지고 뷰는 해제된 메모리를 가리킵니다. SSO 범위의 짧은 문자열은 스택에 있던 버퍼를 가리키게 되어 테스트에서는 멀쩡해 보이다가, 긴 문자열에서만 쓰레기 값이 나오는 식으로 늦게 드러납니다.

std::string makeName() { return "some fairly long generated name"; }

// ❌ 임시 string은 이 줄이 끝나면 소멸
std::string_view name = makeName();
std::cout << name << '\n';  // 해제된 메모리 읽기

// ✅ 소유가 필요하면 string으로 받는다
std::string owned = makeName();
std::string_view view = owned;  // owned보다 오래 쓰지 않는다

string_view는 함수 인자로 받아서 그 함수 안에서만 쓰는 용도가 가장 안전합니다. 멤버 변수나 반환값으로 쓸 때는 원본 문자열의 수명을 누가 보장하는지부터 확인해야 합니다.

---

CSV 파싱, 로그 수집, 설정 파일 파싱 예시

예시 1: CSV 파일 파싱 (행 단위)

#include <fstream>
#include <sstream>
#include <vector>
#include <string>

std::vector<std::vector<std::string>> parseCSV(const std::string& filename) {
    std::ifstream file(filename);
    std::vector<std::vector<std::string>> rows;
    std::string line;

    while (std::getline(file, line)) {
        std::vector<std::string> row;
        std::istringstream iss(line);
        std::string cell;

        while (std::getline(iss, cell, ',')) {
            row.push_back(cell);
        }
        rows.push_back(std::move(row));  // 이동으로 복사 비용 절감
    }
    return rows;
}

설명: CSV 파일을 한 줄씩 읽어 vector<string>으로 쪼개고, std::move로 행을 vector에 넣어 복사를 줄입니다. 행 개수를 미리 알면 rows.reserve(예상_행수)를 추가하면 더 효율적입니다.

추가 최적화: 파일 크기를 std::filesystem::file_size로 미리 알 수 있으면, 한 줄 평균 길이를 가정해 rows.reserve(파일크기 / 평균_줄_길이)로 행 벡터를 reserve할 수 있습니다. 셀 개수가 대략 일정하면 row.reserve(예상_컬럼_수)도 도움이 됩니다.

예시 2: 로그 메시지 수집 (reserve 활용)

#include <vector>
#include <string>
#include <chrono>

std::vector<std::string> collectLogs(int max_entries) {
    std::vector<std::string> logs;
    logs.reserve(max_entries);  // 최대 개수 예상

    for (int i = 0; i < max_entries; ++i) {
        auto now = std::chrono::system_clock::now();
        auto time = std::chrono::system_clock::to_time_t(now);
        std::string msg = "Log entry " + std::to_string(i) + " at " + std::to_string(time);
        logs.push_back(std::move(msg));
    }
    return logs;
}

설명: 로그 개수 상한을 알 때 reserve로 재할당을 막으며, std::move로 string 복사를 줄입니다.

예시 3: 설정 파일 키-값 파싱 (string 최적화)

#include <string>
#include <sstream>
#include <vector>

std::string parseConfigValue(const std::string& line) {
    size_t pos = line.find('=');
    if (pos == std::string::npos) return "";

    std::string value = line.substr(pos + 1);
    // 앞뒤 공백 제거
    size_t start = value.find_first_not_of(" \t");
    size_t end = value.find_last_not_of(" \t");
    if (start == std::string::npos) return "";
    return value.substr(start, end - start + 1);
}

설명: find로 = 위치를 찾으며, substr로 값 부분을 추출합니다. npos 검사를 꼭 해야 합니다.

성능 비교 표

시나리오	reserve가 줄여 주는 것	차이가 커지는 조건
100만 개 int push_back	재할당 약 20회와 그때의 원소 이동	원소 수가 많고 루프만 따로 잴 때
10만 개 string push_back	재할당 횟수 (문자 데이터는 이동이라 복사 안 함)	이동 생성자가 noexcept가 아닌 타입일 때
1만 번 string +=	문자열 버퍼 재할당	최종 길이가 길 때
emplace_back vs push_back	임시 객체 생성 한 번 (생성자 인자를 넘길 때만)	생성·이동 비용이 큰 타입일 때

참고: 실제 차이는 아래 벤치마크 코드로 자기 환경에서 측정해 보세요.

---

reserve 유무와 재할당 횟수 벤치마크

실제 측정 가능한 벤치마크 코드와 결과 해석입니다.

벤치마크 코드 (복사해 실행 가능)

#include <vector>
#include <chrono>
#include <iostream>

template<typename Func>
long long measure_ms(Func&& f) {
    auto start = std::chrono::high_resolution_clock::now();
    f();
    return std::chrono::duration_cast<std::chrono::milliseconds>(
        std::chrono::high_resolution_clock::now() - start).count();
}

int main() {
    const size_t N = 1'000'000;
    auto t1 = measure_ms([&] {
        std::vector<int> v;
        for (size_t i = 0; i < N; ++i) v.push_back(static_cast<int>(i));
    });
    auto t2 = measure_ms([&] {
        std::vector<int> v;
        v.reserve(N);
        for (size_t i = 0; i < N; ++i) v.push_back(static_cast<int>(i));
    });
    std::cout << "int " << N << ": no_reserve=" << t1 << "ms, reserve=" << t2 << "ms\n";
    return 0;
}

g++ -O2 -std=c++17로 컴파일해 실행합니다. string, emplace_back 벤치마크도 동일한 measure_ms 패턴으로 추가할 수 있습니다.

벤치마크 결과 해석 (참고)

테스트	예상되는 경향	이유
int 100만 push_back	reserve 쪽이 빠르지만 루프만 잴 때 차이가 뚜렷하고, 입력 처리와 섞이면 작아짐	재할당 약 20회 동안 옮기는 총량은 최종 크기의 두 배 정도
string 10만 push_back	차이가 int보다 작을 수 있음	std::string은 이동 생성자가 noexcept라 재할당 때 문자 데이터를 복사하지 않고 내부 포인터만 옮김
큰 객체 emplace vs push	생성자 인자를 넘길 때만 emplace가 임시 객체 하나를 줄임	이미 만든 객체를 넘기면 둘은 같은 이동을 함

주의: CPU 캐시, 메모리 대역폭, OS 스케줄링에 따라 결과가 달라집니다. -O2 이상 최적화를 켜고, 여러 번 실행해 평균을 보는 것이 좋습니다.

재할당 횟수 확인

capacity가 바뀔 때마다 재할당이 발생합니다. 100만 개 push_back 시 약 20회, reserve(1000000) 후에는 0회입니다.

---

string 빌더, 컨테이너 선택, shrink_to_fit 시점

버퍼를 clear() 후 재사용하는 패턴과 파일 크기로 원소 수를 추정해 reserve하는 패턴은 #13-1에 있으므로, 여기서는 문자열 조립과 컨테이너 선택만 다룹니다.

string 빌더: 총 길이를 먼저 계산해 한 번만 할당

std::string buildMessage(const std::vector<std::string>& parts) {
    size_t total = 0;
    for (const auto& p : parts) total += p.size();
    std::string result;
    result.reserve(total + parts.size());
    for (size_t i = 0; i < parts.size(); ++i) {
        if (i > 0) result += ", ";
        result += parts[i];
    }
    return result;
}

총 길이를 미리 계산해 reserve하면 += 반복 시 재할당을 피할 수 있습니다.

vector와 다른 컨테이너 중 고르기

상황	추천	이유
인덱스 접근, 끝에 추가	vector	연속 메모리, O(1) 접근
앞에 삽입/삭제	deque 또는 list	vector는 앞 삽입이 O(n)
키로 검색	map / unordered_map	vector는 find가 O(n)
정렬 유지	set / multiset	vector는 sort 후 별도 관리
중복 제거	vector + sort + unique	또는 set으로 직접

vector가 유리한 경우: 대량의 데이터를 순차적으로 읽거나, 인덱스로 자주 접근하거나, 끝에만 추가·삭제할 때. 캐시 지역성이 좋아서 대용량 처리에서도 성능이 뛰어납니다.

shrink_to_fit 사용 시점

shrink_to_fit()은 “capacity를 size에 맞게 줄여도 된다”고 구현에 요청하는 것입니다. 다음 상황에서 고려할 수 있습니다:

• 대량 삭제 후: vec.resize(100)으로 1000개에서 100개로 줄인 뒤, 메모리를 반환하고 싶을 때
• 장기 실행 프로세스: 메모리 사용량을 줄여야 하는 서버 등
• 벤치마크/테스트: reserve 없이 삽입한 뒤, 최종 size에 맞게 메모리를 정리할 때

주의: shrink_to_fit()은 요청일 뿐, 구현이 반드시 줄인다는 보장은 없습니다. 또한 재할당이 일어나므로 비용이 듭니다. 자주 호출하지 말고, “한 번 크게 줄인 뒤 더 이상 수정하지 않을” 벡터에 사용하는 것이 좋습니다.

---

같이 보면 좋은 글

• C++ 기술 면접 질문 30선: 포인터·RAII·가상 함수·STL·동시성 답변 정리
• C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
• C++ 코딩 테스트 준비: 백준·프로그래머스 유형별 STL 활용과 입출력 최적화
• C++ map vs unordered_map (STL 시리즈)
• C++ 람다 표현식 | 캡처·mutable·제네릭 람다와 재귀 람다
• C++ 람다 심화 | 초기화 캡처·완벽 전달·IIFE·재귀 람다와 실전 패턴
• std::vector 제대로 쓰기

---

자주 묻는 질문 (FAQ)

Q. push_back 뒤에 기존 포인터나 반복자가 망가지는 이유는 무엇인가요?

A. size가 capacity에 도달한 상태에서 push_back을 하면 vector는 더 큰 버퍼를 새로 할당하고 원소를 옮긴 뒤 기존 메모리를 해제합니다. 이때 이전에 얻어 둔 반복자, 참조, data() 포인터는 모두 해제된 메모리를 가리키게 됩니다. 원소 개수를 대략 알면 reserve로 재할당을 막고, 오래 보관해야 하는 위치는 포인터 대신 인덱스로 저장하는 편이 안전합니다.

Q. reserve를 너무 크게 잡으면 어떻게 되나요?

A. 메모리만 더 사용합니다. reserve는 “최소 이만큼” 공간을 요청하는 것이므로, 100만 개 넣을 곳에 1000만으로 reserve해도 동작에는 문제 없지만, 사용하지 않는 900만 개치 메모리가 남습니다. 대략적인 상한만 예상해 두는 것이 좋습니다.

Q. emplace_back을 항상 써야 하나요?

A. 복사/이동 비용이 있는 타입(예: string, 사용자 정의 클래스)일 때 유리합니다. int처럼 단순 타입은 push_back과 차이가 거의 없습니다. emplace_back은 생성자 인자를 직접 넘기므로, vec.emplace_back(1, 2)처럼 쓰면 됩니다.