C++ 표준 컨테이너 - vector 재할당과 반복자 무효화, map 과 unordered_map (C++ 객체와 자원 관리 6장)

이 장에서 배우는 것

std::vector, std::string, std::map은 가장 많이 쓰는 RAII 객체다. 원소들의 메모리를 소유하고, 소멸할 때 원소를 모두 정리한다. 그래서 대부분의 코드에서 new[]를 쓸 일이 없다. 하지만 컨테이너가 내부 메모리를 스스로 옮기는 순간이 있고, 그때 바깥에 들고 있던 참조·포인터·반복자는 조용히 무효가 된다. 이 장의 중심은 그 순간이다.

• size와 capacity를 찍어 vector가 언제 새 메모리로 이사하는지 확인하고, reserve로 이사를 막는다.
• 이사 뒤 옛 참조를 읽으면 오류 없이 틀린 값이 나오는 버그를 본다.
• 순회하며 지우는 루프의 정석(erase 반환값, C++20 std::erase_if)을 익힌다.
• std::map과 std::unordered_map의 차이, operator[]가 읽기만 해도 원소를 만드는 함정을 본다.

문제 상황

로봇에 연결된 센서 이름 목록을 std::vector<std::string>으로 관리한다. 메인 루프는 첫 번째 센서(주 센서)의 이름을 자주 쓰니 참조로 붙잡아 두었다. 그런데 실행 중에 새 센서가 꽂혀 목록에 추가되었다.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> sensors{"lidar_front_left_unit", "imu_main_board_unit"};
    const std::string& first = sensors.front();
    std::cout << "추가 전: " << first << std::endl;

    sensors.push_back("gps_receiver_backup_unit");

    std::cout << "추가 후: " << first << std::endl;
}

$ clang++ -std=c++20 -Wall -Wextra invalidation_bug.cpp -o invalidation && ./invalidation
추가 전: lidar_front_left_unit
추가 후: 

추가 전에는 이름이 잘 나왔는데, 추가 후에는 빈 문자열이 나왔다. 프로그램은 죽지 않았고 종료 코드도 0이다. 로그에는 빈 센서 이름이 찍히고, 이 이름으로 설정을 찾는 코드는 "센서 없음"으로 처리할 것이다. 원인은 코드가 아니라 먼 곳에 있는 push_back 한 줄이다.

vector는 원소를 연속된 메모리 한 덩어리에 담는다. 자리가 꽉 찬 상태에서 원소를 더 넣으면 더 큰 덩어리를 새로 얻고, 원소를 그리로 옮기고(4장의 이동), 옛 덩어리를 해제한다. first는 옛 덩어리 안의 문자열을 가리키고 있었으므로 이미 해제된 메모리를 읽은 것이다. 이번 실행에서는 빈 문자열이 나왔지만 이것은 우연이다. 이런 해제 후 사용(use-after-free)은 ASan 같은 도구로 잡아야 하는데, 12장에서 다룬다.

완성 코드

먼저 이사가 언제 일어나는지 확인하는 vector_growth.cpp다. 주소가 바뀌었는지만 출력한다(주소 값 자체는 실행할 때마다 다르다).

#include <iostream>
#include <vector>

int main() {
    std::vector<int> samples;
    const int* last_data = samples.data();
    for (int i = 1; i <= 9; ++i) {
        samples.push_back(i);
        bool moved = samples.data() != last_data;
        std::cout << "size " << samples.size() << ", capacity " << samples.capacity()
                  << (moved ? "  <- 새 메모리로 이사" : "") << '\n';
        last_data = samples.data();
    }

    std::vector<int> reserved;
    reserved.reserve(100);
    const int* before = reserved.data();
    for (int i = 0; i < 100; ++i) reserved.push_back(i);
    std::cout << "reserve(100) 뒤 100개 추가: 이사 "
              << (reserved.data() == before ? "없음" : "있음") << '\n';
}

줄별 해설

size()와 capacity()

size는 실제로 들어 있는 원소 수, capacity는 이사하지 않고 담을 수 있는 원소 수다. size가 capacity를 넘으려는 순간 이사가 일어난다.

samples.data() != last_data

data()는 원소 덩어리의 시작 주소다. 이 값이 바뀌었다면 이사한 것이고, 그 전에 얻은 모든 참조·포인터·반복자가 무효가 되었다는 뜻이다.

reserve(100)

원소를 만들지 않고 capacity만 미리 늘린다. 몇 개가 들어올지 알면 reserve로 이사 횟수를 0으로 만들 수 있다. 게임의 한 프레임 안이나 제어 루프 안처럼 메모리 할당 자체를 피하고 싶은 곳에서 특히 중요하다.

실제 실행 결과

$ clang++ -std=c++20 -Wall -Wextra vector_growth.cpp -o vector_growth && ./vector_growth
size 1, capacity 1  <- 새 메모리로 이사
size 2, capacity 2  <- 새 메모리로 이사
size 3, capacity 4  <- 새 메모리로 이사
size 4, capacity 4
size 5, capacity 8  <- 새 메모리로 이사
size 6, capacity 8
size 7, capacity 8
size 8, capacity 8
size 9, capacity 16  <- 새 메모리로 이사
reserve(100) 뒤 100개 추가: 이사 없음

검증 환경의 표준 라이브러리(libc++)는 용량을 1, 2, 4, 8, 16으로 두 배씩 늘렸다. 9개를 넣는 동안 이사가 다섯 번 일어났다. 증가 비율은 표준이 정하지 않으므로 GCC의 libstdc++나 MSVC에서는 다른 숫자가 나올 수 있다(MSVC는 1.5배로 알려져 있다). 확실한 것은 "언제 이사할지 코드만 보고 알 수 없다"는 점이다. 그래서 규칙은 단순해야 한다. 원소를 추가하거나 지우는 연산 뒤에는 그 전에 얻은 참조·포인터·반복자를 버린다.

표 6-1. vector 반복자·참조가 무효가 되는 연산

연산	vector에서 무효가 되는 것
push_back, emplace_back, insert	이사하면 전부. 이사하지 않으면 삽입 위치 이후
erase	지운 위치와 그 이후
reserve, shrink_to_fit	용량이 바뀌면 전부
clear	전부

무효화에 강한 대안은 두 가지다. 원소를 오래 가리켜야 하면 참조 대신 인덱스를 저장한다(이사해도 v[i]는 같은 원소다). 아니면 노드 기반 컨테이너(std::map, std::list)를 쓴다. 이들은 다른 원소를 넣거나 지워도 기존 원소의 참조가 유지된다.

순회하면서 지우기

음수 센서 값을 걸러 내는 코드를 세 가지로 짰다.

#include <iostream>
#include <vector>

void print(const char* label, const std::vector<int>& v) {
    std::cout << label;
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> readings{5, -1, -2, 8, -3, 9};

    std::vector<int> a = readings;
    for (auto it = a.begin(); it != a.end();) {
        if (*it < 0) it = a.erase(it);
        else ++it;
    }
    print("erase 반환값 사용:", a);

    std::vector<int> b = readings;
    auto removed = std::erase_if(b, [](int x) { return x < 0; });
    print("std::erase_if:   ", b);
    std::cout << "지운 개수: " << removed << '\n';

    std::vector<int> c = readings;
    for (auto it = c.begin(); it != c.end(); ++it) {
        if (*it < 0) c.erase(it);
    }
    print("잘못된 루프:     ", c);
}

$ clang++ -std=c++20 -Wall -Wextra erase_loop.cpp -o erase_loop && ./erase_loop
erase 반환값 사용: 5 8 9
std::erase_if:    5 8 9
지운 개수: 3
잘못된 루프:      5 -2 8 9

첫 번째는 erase가 돌려주는 "지운 원소 다음 위치"를 받아서 계속한다. 지웠을 때는 ++it를 하지 않는 것이 요점이다. 두 번째는 C++20의 std::erase_if로, 같은 일을 한 줄로 하고 지운 개수까지 돌려준다. 새 코드라면 이것을 쓴다. 세 번째 루프는 erase 뒤 무효가 된 it를 계속 쓴다. 이번 실행에서는 죽지 않고 -2가 살아남은 틀린 결과가 나왔다. -1을 지우면서 -2가 그 자리로 당겨졌는데, 루프가 ++it로 그 자리를 건너뛰었기 때문이다. 연속된 음수가 없는 테스트 데이터였다면 통과했을 것이다.

std::map과 std::unordered_map

#include <iostream>
#include <map>
#include <stdexcept>
#include <string>
#include <unordered_map>

int main() {
    std::map<std::string, int> stock{{"bolt", 120}, {"nut", 80}, {"gear", 4}};

    std::cout << "1) map 은 키 순서로 돈다\n";
    for (const auto& [part, count] : stock) std::cout << "  " << part << " = " << count << '\n';

    std::cout << "2) operator[] 로 읽기만 해도 생긴다\n";
    std::cout << "  size 전 " << stock.size();
    int spring = stock["spring"];
    std::cout << ", spring=" << spring << ", size 후 " << stock.size() << '\n';

    std::cout << "3) 읽기 전용이면 find/contains/at\n";
    if (auto it = stock.find("gear"); it != stock.end()) std::cout << "  gear 재고 " << it->second << '\n';
    std::cout << "  motor 있음? " << std::boolalpha << stock.contains("motor") << '\n';
    try {
        std::cout << stock.at("motor") << '\n';
    } catch (const std::out_of_range& e) {
        std::cout << "  at 예외: " << e.what() << '\n';
    }

    std::cout << "4) insert_or_assign / try_emplace\n";
    stock.insert_or_assign("gear", 10);
    stock.try_emplace("gear", 999);
    std::cout << "  gear = " << stock["gear"] << '\n';

    std::cout << "5) unordered_map: 해시, 순서 보장 없음\n";
    std::unordered_map<std::string, int> hits;
    for (const char* w : {"jump", "run", "jump", "idle", "jump", "run"}) ++hits[w];
    std::cout << "  jump=" << hits["jump"] << " run=" << hits["run"] << " idle=" << hits["idle"] << '\n';
    std::cout << "  원소 " << hits.size() << "개, 버킷 " << hits.bucket_count() << "개\n";
}

$ clang++ -std=c++20 -Wall -Wextra map_demo.cpp -o map_demo && ./map_demo
1) map 은 키 순서로 돈다
  bolt = 120
  gear = 4
  nut = 80
2) operator[] 로 읽기만 해도 생긴다
  size 전 3, spring=0, size 후 4
3) 읽기 전용이면 find/contains/at
  gear 재고 4
  motor 있음? false
  at 예외: map::at:  key not found
4) insert_or_assign / try_emplace
  gear = 10
5) unordered_map: 해시, 순서 보장 없음
  jump=3 run=2 idle=1
  원소 3개, 버킷 5개

표 6-2. 컨테이너별 연산 비용

컨테이너	찾기	끝에 추가	중간 삽입·삭제
vector	O(n), 정렬돼 있으면 O(log n)	평균 O(1)	O(n)
map	O(log n)	O(log n)	O(log n)
unordered_map	평균 O(1)	평균 O(1)	평균 O(1)
list	O(n)	O(1)	위치를 알면 O(1)

• 순서 — map은 키를 정렬해 보관한다(보통 균형 이진 트리). 넣은 순서와 상관없이 bolt, gear, nut 순으로 돈다. unordered_map은 해시 표라서 순회 순서가 정해져 있지 않다. 이 예제에서 순회 출력 대신 키로 직접 읽은 이유다.
• operator[] — 키가 없으면 기본값(int는 0)으로 원소를 만들어 넣고 그 참조를 돌려준다. spring을 읽기만 했는데 크기가 3에서 4가 되었다. 오타 난 키로 조회하면 쓰레기 원소가 쌓인다. 개수 세기(++hits[w])처럼 "없으면 0에서 시작"이 의도일 때만 쓴다.
• 읽기 전용 — find(반복자, 없으면 end()), contains(C++20, bool), at(없으면 std::out_of_range 예외)을 쓴다. const map에는 operator[]가 아예 없다.
• 쓰기 — insert_or_assign은 있으면 덮어쓰고, try_emplace는 이미 있으면 아무것도 하지 않는다. 그래서 gear는 999가 아니라 10이다.
• 성능 — map은 찾기가 O(log n), unordered_map은 평균 O(1)이다. 원소가 적거나 정렬된 순회가 필요하면 map, 많은 키를 빠르게 찾기만 하면 unordered_map이 보통 유리하다. 버킷 수는 구현이 정하므로 출력된 5라는 숫자에 의미를 두지 않는다.

실무에서 자주 틀리는 것

1. 원소 참조를 쥔 채 같은 vector에 추가한다

문제 상황 그대로다. 한 함수 안에서는 눈에 띄지만, 참조를 멤버로 저장해 두고 다른 함수에서 push_back 하면 리뷰로 찾기 어렵다. vector 원소를 가리키는 참조·포인터를 멤버로 저장하는 설계 자체를 의심한다.

2. 범위 기반 for 안에서 같은 컨테이너를 바꾼다

for (auto& s : sensors) if (...) sensors.push_back(...);는 루프가 내부적으로 쥔 반복자를 무효로 만든다. 추가할 것을 별도 목록에 모았다가 루프 뒤에 합친다.

3. v[i]의 범위를 믿는다

operator[]는 범위를 검사하지 않는다. 범위 밖이면 정의되지 않은 동작이다. 입력에서 온 인덱스는 at()(예외)으로 읽거나 먼저 검사한다. 개발 빌드에서는 표준 라이브러리 검사 모드를 켜서 잡는다(12장).

4. unordered_map 순회 순서에 기대는 테스트

한 컴퓨터에서 매번 같은 순서가 나와도, 다른 표준 라이브러리나 원소 수가 달라지면 순서가 바뀐다. 출력 순서가 중요하면 키를 뽑아 정렬하거나 map을 쓴다.

연습 문제

1. 문제 상황의 코드에서 참조 대신 무엇을 저장하면 push_back이 몇 번 일어나도 주 센서 이름을 안전하게 읽을 수 있는가?
2. std::map<int, std::string> m{{1, "one"}}; std::string& one = m[1]; 다음 원소 1,000개를 더 넣었다. one은 여전히 안전한가? vector와 무엇이 다른가?
3. 함수 int stock_of(const std::map<std::string, int>& m, const std::string& key) 안에서 return m[key];는 컴파일되지 않는다. 왜 그런가? 대신 무엇을 쓰는가?

정답

1. 인덱스(std::size_t primary = 0;)를 저장하고 쓸 때마다 sensors[primary]로 읽는다. 이사하면 주소는 바뀌지만 인덱스가 가리키는 원소는 같다. 앞쪽 원소를 지우면 인덱스도 어긋나므로, 삭제가 있는 구조라면 센서마다 고유 ID를 두고 map으로 찾는 방법이 더 안전하다. 검증 프로그램에서 원소 50개를 추가한 뒤 인덱스로 같은 원소를 읽는 것을 확인했다.
2. 안전하다. map은 원소마다 노드를 따로 할당하고, 삽입은 노드끼리의 연결만 바꾼다. 기존 노드는 움직이지 않으므로 참조가 유지된다(그 원소를 erase 하면 무효). vector는 원소들을 한 덩어리에 담아 통째로 옮기기 때문에 다르다. 검증 프로그램에서 1,000개 삽입 뒤 &one == &m[1]을 확인했다.
3. operator[]는 키가 없으면 원소를 만들어야 하므로 const map에서는 쓸 수 없다. 없는 키에 대한 정책에 따라 m.at(key)(없으면 예외) 또는 auto it = m.find(key); return it == m.end() ? 0 : it->second;를 쓴다.

다음 장에서는 이 컨테이너들을 반복문 대신 표준 알고리즘과 람다로 다룬다. 람다가 바깥 변수를 참조로 붙잡을 때 생기는 수명 문제도 함께 본다.