iterator 사용 시 흔히 하기 쉬운 실수
C++ 개발자라면 무조건 알아야 하는 주의 사항
iterator 사용 시 push, emplace 사용 시 발생하는 버그
iterator를 사용하면 C++에서 STL 라이브러리들을 쉽게 다룰 수 있습니다. iterator에 대한 글을 보고 싶다면 iterator, 왜 사용할까?라는 글을 참고하세요.
vector를 사용할 때 iterator는 아주 유용하죠. 그런데 vector iterator 사용 시 모든 사람이 꼭 알아야 주의해야 할 점이 있습니다. 바로 iterator 사용 시 그 안에서 push_back, emplace_back과 같은 연산을 사용해선 안 된다는 것입니다. 이건 정말 C++를 다루는 사람이라면 반드시 알아둬야 할 사항이고, 이로 인해 심각한 버그도 발생할 수 있습니다. 그리고 이 행위는 컴파일러 등에 의해서 오류로 찾아지지도 않습니다.
다음 코드를 한 번 봅시다.
#include <iostream>
#include <vector>
int main()
{
std::vector<int> nums = { 1, 2, 3, 4, 5 };
auto is_even = [](int num) { return num % 2 == 0; };
for (std::size_t index = 0; index < nums.size(); index++) {
if (is_even(nums[index])) {
nums.emplace_back(-1);
}
}
for (const auto num : nums) {
std::cout << num << ' ';
}
return 0;
}위 코드는 nums를 시작부터 끝까지 돌면서, 만약 짝수를 만나면 그 뒤에 -1을 삽입하는 코드입니다. 위 코드의 결과는 아래와 같습니다.
결과:
1 2 3 4 5 -1 -1짝수가 2와 4밖에 없으므로 -1은 맨 뒤에 두 개만 삽입되었습니다.
그런데 이를 iterator를 사용해서 한 번 바꿔보겠습니다. 똑같은 로직으로요.
auto is_even = [](int num) { return num % 2 == 0; };
for (auto iter = nums.begin(); iter != nums.end(); iter++) {
if (is_even(*iter)) {
nums.emplace_back(-1);
}
}결과:
Segmentation fault가 뜬 것을 볼 수가 있어요. 런타임 과정 중에 메모리 상의 문제가 생겼다는 의미에요.
중요한 점은 심지어 모든 경고를 에러로 표시해주는 -Wall 옵션을 주었음에도 컴파일러는 아무 문제 없이 코드를 컴파일했다는 게 문제죠.
여기서는 Segmentation fault 에러가 떴고, gcc 외 msvc, clang 등을 사용했을 때에도 그냥 프로그램이 종료됐는데, 간혹가다간 또 정상적으로 실행될 수도 있습니다.
이게 제일 무서운 버그인건데, 디버깅 과정 중에서는 보이지 않다가 실제 배포하고나서 문제가 생길 수가 있는 버그에요.
왜 이런 결과가 나온 걸까요? 그 이유를 알기 위해선 먼저 벡터의 메모리 구조에 대해서 알아야 합니다.
버그가 발생하는 이유
벡터의 메모리 구조
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v = {1, 2, 3};
v.emplace_back(4);
return 0;
}위와 같은 코드가 있다고 하였을 때, v를 다음 그림과 같이 나타낼 수 있습니다.
스택 위에 올라간 v가 힙 공간에 생성된 메모리 블럭 1, 2, 3을 가리키고 있습니다. 이때 그 뒤에 비어있는 공간이 있을 수도, 혹은 그림처럼 다른 곳에서 사용중인 메모리가 이미 채워져있을 수도 있습니다. 그런데 이때 v에 emplace_back(4) 연산을 해서 뒤에 새로운 원소를 추가한다고 해봅시다. 이때 4라는 새로운 원소가 들어갈 공간이 없으므로, 벡터 마이그레이션이라는 연산이 일어나게 됩니다.
새로운 원소 4를 추가한다 하였을 때 뒤에 공간이 이미 다른 메모리로 채워져있다면
적당히 넓은 새로운 공간으로 이동하게 됩니다. 즉 n개의 원소가 근처의 새로운 Heap 영역으로 이사를 가고, 메모리의 주소가 아예 바뀌게 됩니다.
참고로 그림에서는 3개의 원소로 공간을 표현했는데, 실제로 대부분의 컴파일러에서는 2, 4, 8 ... 이런 식으로 2의 배수 형태로 그 크기를 늘려나간다는 것을 기억하세요.
암튼 우리가 그냥 아무 생각 없이 크기가 변하는 다이나믹 어레이를 사용했었는데, 그 이면에는 이런 힙 할당 연산이 숨어있던 것입니다. 사실 C언어를 어느정도 제대로 공부하였다면 이미 알고 계셨을 수도 있을 겁니다.
문제는 이 벡터 마이그레이션 때문에, iterator 사용시 바로 문제가 발생합니다.
iterator 사용 시 버그가 발생하는 이유
코드의 상황이 딱 비슷한 상황이에요.
- 처음엔 iterator가 제대로 돌고 있죠?
- 근데 갑자기 뒤에 새로운 원소를 삽입하려 합니다? iterator가 놀란 표정을 하고 있네요. 새로운 원소를 추가하려고 하는데 뒤에 공간이 없습니다. 그래서 더 넓은 새로운 공간으로 n개의 원소가 이사를 갑니다. 벡터 마이그레이션이 일어났습니다.
- 문제는 iterator는 우리가 원하는 만큼 똑똑하지 않아서, 벡터 원소들이 함께 이사를 갔는데도 그 사실을 모르고, 여전히 같은 자리를 돌고 있습니다. 4. 무의미한 공간을 돌면서, 저 뒤에 주황색 쓰레기 값도 읽어주고, 이후에 1, 2, 3, 4, 5를 읽은 후 end()를 만나서 연산을 종료할 겁니다. 그 와중에 만약 한 번 더 벡터 마이그레이션이 일어난다면, 혹은 이동한 공간이 너무 멀리 떨어져있다면, iterator는 잘못하면 계속 무의미한 공간을 헛돌수도 있습니다.
문제는 이게 컴파일 에러가 아니다 보니깐 생각 없이 코드 짜다가 자주 발생할 수 있는 문제라는 거예요.
사실 그래서 만약 emplace, push등의 연산이 필요하다면 처음 코드와 같이 그냥 index를 사용하는 게 제일 안전합니다.
결론
iterator 사용 시 push_back, emplace_back 사용에 매우 주의해야 합니다.
여담으로 reserve라는 함수를 통해, 미리 벡터에게 할당될 공간을 예약할 수 있습니다. 왜냐면 마이그레이션 역시 n개의 원소가 새로운 공간으로 이동해야 하므로 O(n)시간이 소요되어서, 실제로 reserve를 하고 말고의 성능 차이가 크게 발생하거든요. 그래서 reserve를 통해 마이그레이션을 최대한 줄이거나 없앤다는 점도 기억해두시면 좋습니다.