개요

앞 편 5번에서 재할당이 일어나면 기존 원소의 수명이 끝난다는 데까지 왔다. 그럼 그 원소를 가리키고 있던 iterator는 어떻게 되는가 — 이번 편이 그 자리다.

여기서 두 번 걸렸다. 하나는 무효화의 기준을 주소로 보고 있었다는 것이고, 다른 하나는 iterator를 포인터의 다른 이름으로 보고 있었다는 것이다. 설명해보라고 해서 답했다가 둘 다 어긋났는데, 쓰다 보니 두 오해가 같은 뿌리였다.

후반부는 unordered_map 쪽이다. 여기서도 “key를 해시해서 값에 바로 접근한다”는 그림을 들고 있었는데, 한 단계가 빠져 있었다.

  • 주소로 설명하면 반쯤만 맞는 것 — iterator도, 무효화도 여기서 걸렸다
  • 비슷해 보여서 붙여 쓰던 것 — 적재율과 충돌을 거의 같은 말로 쓰고 있었다
  • 한 단계를 통째로 건너뛴 것 — 해시값이 바로 값을 가리킨다고 봤다

주소가 그대로인데 왜 못 쓰는가? 이번 편은 이 질문에서 시작한다.

( 진행 방식은 앞 편과 같다. 직접 컴파일해서 돌려보지는 않았고, 아래 코드는 전부 개념 예시다 )

1. iterator는 포인터의 별명이 아니다

내 머릿속에서 iterator는 대충 주소를 들고 다니는 물건이었다. v.begin()은 첫 원소 주소, ++는 주소를 sizeof만큼 밀기.

vector만 보면 이 그림으로도 굴러간다. 그런데 list iterator에 + 3을 못 붙이는 이유를 설명하려니 바로 막혔다.

정확한 쪽은 이렇다.

iterator(반복자)는 컨테이너 안의 현재 위치와, 그 자료구조에서 허용되는 순회·접근 연산을 함께 추상화한 객체다.

즉 “어디”뿐 아니라 “여기서 뭘 할 수 있는가”가 타입에 들어 있다.

iterator 성질 할 수 있는 것
vector random access iterator(임의 접근) ++, --, it + 3, it2 - it1
list bidirectional iterator(양방향) ++, -- 까지

list가 it + 3을 제공하지 않는 건 인색해서가 아니라, 그 자료구조에서 그 연산이 O(1)이 아니기 때문이다. 세 칸을 가려면 노드를 세 번 따라가야 한다. iterator 타입이 자료구조의 실제 비용 구조를 그대로 반영하고 있는 셈이다.

vector iterator가 포인터처럼 동작할 수 있는 것과 포인터인 것은 다른 이야기였다.

2. 무효화는 “주소에 값이 남아 있느냐”가 아니다

insert()가 왜 iterator를 무효화하느냐는 질문에 나는 이렇게 답했다.

기존 주소값을 변경하거나 참조를 끊기 때문

재할당이 일어나는 경우만 생각하면 맞는 말이다. 저장 공간 자체가 새로 잡히니 예전 주소는 남의 땅이 된다.

문제는 재할당이 안 일어나는 경우다.

std::vector<int> v{10, 20, 30};
v.reserve(100);          // capacity 넉넉함, 재할당 없음

int* p = &v[2];          // 값 30을 가리킨다
v.insert(v.begin(), 999);

capacity가 남아 있으니 저장 공간 시작 주소는 그대로다. p가 가리키는 메모리 번지도 그대로 존재한다. 그럼 p는 유효한가?

아니다. 삽입 지점 뒤의 원소들이 한 칸씩 밀렸기 때문에, p가 있던 자리에는 이제 30이 아니라 20이 들어있다. 주소는 살아 있는데 의미가 바뀌었다.

그래서 invalidated(무효화)의 기준은 이쪽이었다.

그 핸들을 C++ 규칙상 계속 유효하게 사용할 수 있다고 보장되는가

“주소에 뭔가 값이 있느냐”가 아니라 보장이 살아 있느냐다. 이게 1번과 이어진다. iterator를 주소로만 보고 있으면 무효화도 주소 문제로만 보인다.

정리하면

상황 무효화 범위
재할당이 일어나는 insert 전부 — iterator, reference, pointer 모두
재할당이 없는 insert 삽입 지점과 그 이후
erase 삭제 지점과 그 이후

지점 자체도 포함이다. 밀려난 원소가 그 자리부터 시작하기 때문에, 딱 그 위치를 가리키던 핸들이 제일 먼저 어긋난다.

std::vector<int> v{10, 20, 30, 40};

auto a = v.begin();     // 10
auto b = v.begin() + 2; // 30

v.erase(v.begin() + 1); // 20 삭제
  • a — 삭제 지점 앞 → 그대로 유효
  • b — 삭제 지점 뒤 → 무효

b가 가리키던 번지에는 이제 40이 들어와 있다. 여기서도 문제는 주소가 아니라 밀린 원소다.

3. 그래서 erase()가 iterator를 돌려준다

이건 지금까지 그냥 “편의상 반환하나 보다” 하고 썼던 부분이다.

for (auto it = v.begin(); it != v.end(); )
{
    if (*it % 2 == 0)
        it = v.erase(it);  // 반환값을 받아야 한다
    else
        ++it;
}

erase(it) 이후 it은 무효다. 그걸 그대로 ++ 하면 안 된다. 그래서 표준이 삭제 다음 위치의 유효한 iterator를 돌려주는 것이었다. 편의 기능이 아니라 무효화 규칙 때문에 필요한 반환값이었다.

원래 알고 있던 건 “루프 안에서 지울 땐 반환값을 받아야 한다”는 사용법이었고, 왜는 여기서 붙었다.

4. 해시 테이블 — 한 단계가 빠져 있었다

내 그림은 이랬다.

key를 해시해서 그 결과로 Value에 직접 접근한다

실제로는 중간에 한 단계가 더 있다.

Key
 -> hash function(해시 함수)
 -> hash value(해시값)
 -> bucket index(버킷 위치)
 -> 그 bucket 안의 후보 key들과 실제 비교
 -> Value

해시값은 값의 위치가 아니라 bucket(버킷)의 위치를 정한다. 그리고 그 버킷 안에서 key를 실제로 비교하는 단계가 남아 있다.

이 단계가 왜 필요한지는 다음 문단에서 바로 나온다. 서로 다른 key가 같은 버킷에 들어올 수 있기 때문이다. 비교 없이 버킷만 보고 값을 돌려주면 남의 값을 돌려주게 된다.

그래도 전체 N개를 처음부터 훑는 것보다는 훨씬 적은 후보만 보면 되니, 평균적으로는 O(1)에 가까운 탐색이 된다. 앞 편 4번에서 “평균 경우의 Big-O를 쓸 수도 있다”고 적었는데, 그 예시가 정확히 여기다.

5. 충돌과 적재율은 같은 말이 아니다

이 둘을 거의 붙여서 쓰고 있었다. 적재율이 높으면 충돌이 많고, 낮으면 적다 — 대충 이런 식이었다.

load factor(적재율) = 원소 수 / 버킷 수

적재율은 버킷 하나당 평균 원소 수를 나타내는 지표다. 평균이다.

collision(충돌)은 서로 다른 key가 같은 버킷 후보로 들어가는 현상이다. 원래 해시값이 같아서일 수도 있고, 해시값은 다른데 버킷 개수로 줄이는 과정에서 같아질 수도 있다.

둘이 다른 이유는 이 예시에서 드러난다.

원소 버킷 적재율
1000개 100개 10
1000개 2000개 0.5

아래쪽은 적재율이 0.5로 아주 낮다. 그런데 해시 함수가 나빠서 1000개가 버킷 몇 개에 몰려 있다면 그 버킷을 조회할 때는 후보를 잔뜩 비교해야 한다. 평균은 0.5인데 실제로 가는 자리는 붐빈다.

적재율이 낮아도 hash distribution(해시 분포)이 나쁘면 특정 버킷에 몰려서 느려질 수 있다.

여기서 표현 하나를 더 고쳤다. “나쁜 해시 함수가 큰 버킷을 만든다”고 적었는데, 버킷의 크기를 만드는 게 아니라 특정 버킷에 원소가 과도하게 몰리게 하는 것이다.

unordered_map의 최악이 O(N)인 이유가 이거였다. 전부 한 버킷에 몰리면 결국 선형 탐색이다.

6. rehash — 버킷 수가 바뀌면 전부 다시 배치해야 한다

적재율이 너무 높아지면 버킷 수를 늘린다. 그런데 버킷 수가 바뀌면 key → 버킷 매핑 자체가 달라진다. 해시값을 버킷 개수로 줄이는 단계가 바뀌기 때문이다.

그래서 기존 원소들을 새 기준으로 다시 배치해야 한다. 이게 rehash(재해싱)이고, 개념적으로 O(N)짜리 작업이다.

앞 편 6번의 vector 재할당과 같은 모양이다.

  vector unordered_map
언제 capacity 부족 적재율 초과
무슨 일 새 저장 공간으로 전부 이동 새 버킷 기준으로 전부 재배치
비용 O(N) 한 번 O(N) 한 번
평소 상각하면 싸다 상각하면 싸다
프레임 단위로 보면 그 프레임만 튄다 그 프레임만 튄다

이 표를 만들고 나니 궁금해진 게 있었다. 한 번에 다 옮기지 말고 조금씩 나눠서 옮기면 안 되나?

가능하다. incremental rehashing(점진적 재해싱)이라고 부르는 설계가 있다. 다만 옮기는 중에는 원소가 옛 버킷과 새 버킷에 나뉘어 있으니 탐색할 때 양쪽을 봐야 하고, 구현이 그만큼 복잡해진다.

그리고 이게 유니티 16편에서 좀비 스폰을 여러 프레임에 나눌지 고민하던 것과 같은 종류의 거래라는 걸 알아챘다. 총 작업량은 그대로 두고 한 번에 몰리는 양만 줄이는 것. 자료구조 내부에서도 같은 판단을 하고 있었다.

한 가지는 확인 안 된 채로 남겨둔다. std::unordered_map의 실제 내부 구조는 표준이 세부까지 강제하지 않아서, 구현체마다 다를 수 있다. 여기 적은 건 개념 수준이다.

정리

알고는 있었는데 이유가 없던 것

  • vector iterator에는 + 3이 되고 list는 안 된다 — 자료구조에서 그 연산이 O(1)이 아니기 때문이다
  • 루프 안에서 지울 땐 erase() 반환값을 받아야 한다 — 무효화 규칙 때문에 필요한 반환값이었다
  • unordered_map은 최악 O(N)이다 — 한 버킷에 몰리면 결국 선형 탐색이라서

틀리게 잡고 있던 것

  • iterator는 포인터의 별명이 아니다. 위치 + 허용된 연산의 추상화다
  • 무효화는 주소가 바뀌는 문제가 아니다. 주소가 그대로여도 원소가 밀리면 무효다
  • 해시값은 값의 위치가 아니라 버킷의 위치를 정한다. 버킷 안에서 key 비교가 남는다
  • 적재율과 충돌은 같은 개념이 아니다. 적재율은 평균, 충돌은 분포의 문제다
  • “나쁜 해시가 큰 버킷을 만든다”가 아니라 특정 버킷에 몰리게 한다

이번에 새로 얹은 것

  • 재할당 없는 insert도 삽입 지점과 그 이후를 무효화한다
  • erase는 삭제 지점 이전 iterator는 건드리지 않는다
  • rehash는 버킷 수가 바뀌면 매핑이 달라지기 때문에 필요하다
  • incremental rehashing — 총량은 같고 한 번에 몰리는 양만 줄이는 거래

1번에서 “iterator를 주소로 보고 있었다”가 나오고 2번에서 “무효화를 주소 문제로 보고 있었다”가 나왔는데, 쓰면서 보니 두 번째가 첫 번째의 결과였다. 틀린 그림 하나가 두 자리에서 따로 틀린 답을 만들고 있었다.

다음은 탐색 쪽이다. 이번 편에서 평균 O(1)의 대가로 순서를 포기한 자료구조를 봤으니, 순서를 지키면서 O(log N)을 받는 쪽이 다음 자리다. map과 unordered_map을 놓고 고르는 기준도 거기서 정리한다.

참고 자료

소감

무효화를 “주소가 바뀌어서”로 외우고 있었는데, 재할당 없는 insert 예시 하나에 바로 무너졌다. 주소는 멀쩡한데 값이 밀려 있는 그림을 보고 나서야 보장과 번지는 다른 얘기라는 게 잡혔다. 그리고 rehash를 정리하다가 지난주 유니티에서 스폰을 나눌까 말까 하던 고민이랑 같은 거래라는 걸 알아챘을 때가 오늘 제일 반가웠다..! 손으로 한 판단에 이름이 붙는 게 요즘 계속 이런 식이다.