c++를 어느 정도 쓰기 시작한다면 아마 배열이나 동적할당은 거의 갖다버리고 std::vector를 위주로 쓰게 될 거야.

사실 당연한 게, std::vector는 우리가 동적할당으로 하는 거의 모든 삽질을 훨씬 안전하고 편리하게 쓸 수 있도록 구현된 갓갓 컨테이너 (원소를 여러 개 가지는 자료형)라서 안 쓰는 게 바보인걸.

그런데, std::vector는 생각보다 '사고 치기'도 쉬운 컨테이너야.

std::vector를 잘 쓰면 아주 편리하게 고성능을 뽑아낼 수도 있지만, 잘못하면 최소 개판난 시간복잡도, 좀 더 가면 잘못된 메모리 접근으로 인한 강제종료까지 온갖 재난이 발생하곤 해.

그래서 조금이나마 도움이 되지 않을까 하는 마음으로 std::vector를 쓸 때 유의할 점을 한번 정리해봤어.

0. std::vector는 '연속적인' 메모리 공간을 차지한다

이게 다른 컨테이너와 std::vector의 가장 큰 차이점 중 하나이자, 하술할 별별 문제가 생기는 근본적인 원인이기도 해.

그 이유를 정말정말 많은 내용을 생략하고 간단하게만 설명하자면, 현대 컴퓨터는 캐시 때문에 메모리 주소상 인접한 데이터에 접근하는 속도가 그렇지 않은 데이터보다 압도적으로(100배 정도) 빨라서 그래.

그래서 std::vector는 원소를 순회할 때 이 특성을 활용하기 위해서 모든 원소가 반드시 연속적인 메모리 공간을 차지하도록 (정확히는 그렇게 구현하도록) 아예 언어 표준에 박아버렸어.

1. std::vector는 메모리를 재할당받을 수도 있다

근데 std::vector를 쓰다 보면 원소를 엄청 많이 넣고 빼고 할 텐데, std::vector는 연속적인 메모리 공간을 차지해야 한다는 제약이 있댔지?

만약에 std::vector에서 원소 4개가 들어갈 공간을 할당받았는데, 5번째 원소를 넣어야 할 상황이 오면 어떻게 될까?

원래 갖고 있던 공간 바로 뒤에 추가로 공간을 할당받을 수 있다면 좋겠지만 보통은 그렇게 안 되는 경우가 많아. 메모리를 '어떻게' 할당받을지는 언어나 컴파일러에서 어떻게 할 수 있는 거도 아니고... (이런 건 jemalloc 같은 메모리 관리 라이브러리나 OS의 역할)

그래서 std::vector는 이런 경우엔 갖고 있던 공간의 2배 정도를 새로 할당받아서 -> 기존 공간에 있던 데이터를 전부 복사해온 뒤 -> 기존 공간을 할당 해제하도록 구현돼 있어.

2. std::vector에 원소를 삽입하면 그전에 만든 모든 포인터와 iterator는 invalidate 된다(고 생각해라)

1. 에서 말한 것처럼 std::vector에 원소를 삽입하면 기존 공간이 할당 해제가 돼버릴 수 있어.

근데 삽입하기 전에 특정 원소를 가리키는 포인터나 iterator를 만들어뒀다면 얘들은 할당 해제된 공간의 주소를 가리키는 게 돼버리겠지?

할당 해제된 주소에 접근하는 경우는 undefined behavior인데... 이게 뭔지 설명하려면 글을 하나 더 써야 해서; 일단은 프로그램이 segmentation fault 띄우면서 꺼지거나 전혀 이상한 값이 나와버릴 수 있다고 생각하면 돼. 뭐가 됐든 이런 일이 일어나서는 안 되겠지?

그래서 std::vector에 원소를 삽입한 뒤에는 절대로 기존에 만든 포인터와 iterator를 써서는 안 되고 반드시 새로 만들어야 해.

물론 운이 좋으면 재할당이 안 일어날 수도 있겠지만 내 프로그램의 정상 작동을 운에 맡기면 안 되니까....

3. std::vector에 원소를 그냥 삽입하면 재할당에 엄청난 시간이 걸린다(고 생각해라)

예를 들어서 내가 새로운 std::vector에다가 원소 16385개를 삽입하는 과정을 생각해보면 대략 이래

이런 식으로, 재할당이 한 번 일어날 때마다 지금까지 넣었던 원소들을 전부 복사해야 하다 보니까 단순히 '삽입'만 해도 원래 필요한 일의 2배를 해줘야 해.

문제는 메모리 재할당도 시간이 꽤 오래 걸리는 작업이란 거... 이건 궁극적으로 OS를 거쳐야만 하는 작업이라서 과장 좀 섞자면 걸리는 시간 단위가 달라. 이 예시에서는 재할당도 12번이나 일어났지?

그래서 대책없이 std::vector에 원소를 삽입하면 시간을 엄청나게 낭비하게 돼버려.

물론 운이 좋으면 재할당이 안 일어날 수도 있겠지만 내 프로그램의 성능도 운에 맡기면 안 되니까....

4. std::vector의 원소를 삭제하면 그 뒤에 있던 원소를 전부 앞으로 한 칸씩 당겨온다

앞에서 말한 거와는 조금 다른 얘기인데, 원소들이 연속된 메모리 공간을 차지한다는 제약 때문에 std::vector에서 원소를 삭제한 뒤에는 그 뒤에 붙어 있던 원소를 모두 앞으로 당겨와야 해.

만약 std::vector의 맨 앞에 있던 원소를 삭제한다면? N-1개 원소를 복사해야겠지. 이걸 std::vector가 빌 때까지 반복한다면? 시간 복잡도가 O(N²)가 돼버리는 거야.

그뿐만 아니라 원소들을 당겨오면 포인터나 iterator도 원래 가리키던 원소가 아니라 엉뚱한 원소, 또는 이미 삭제된 원소를 가리키게 될 수 있어. 그래서 삭제한 원소의 뒤를 가리키던 포인터와 iterator는 삽입 때와 마찬가지로 모두 invalidate될 거고, 쓰면 큰일이 나겠지?

참고로 삭제된 원소 앞에 있던 원소들은 위치가 변하지 않기 때문에 포인터나 iterator가 invalidate될 일이 없어.

그러면 이런 지뢰가 있는 줄은 알겠는데, 이 지뢰들을 어떻게 해야 피할 수 있을까?

A. std::vector::reserve()

std::vector에는 reserve라는 멤버 함수가 있는데, 얘는 새로운 원소를 삽입하지는 않고 메모리 공간만 미리 할당받기 위한 함수야. vec.reserve(512); 라고 하면 vec에 원소 512개가 들어갈 만큼의 공간을 미리 할당받는 식.

std::vector를 써서 프로그래밍을 하다 보면 알겠지만, 내가 원소를 최대 몇 개 넣을지 std::vector를 생성하는 시점에서 알 수 있는 경우가 생각보다 정말 많아. 체감상으론 한 90%는 되는 거 같아.

std::vector를 생성할 때마다 reserve를 항상 같이 해주면 삽입을 훨씬 효율적으로 할 수 있겠지.

예를 들어 3. 에서 예시로 들었던 원소 16385개 삽입을 reserve를 활용해서 최적화하면 이렇게 돼.

reserve 한 번만으로 재할당과 복사를 전부 없애버린 게 보이지? 사실 이거 하나만으로 1. 2. 3. 의 문제를 대부분 다 해결할 수 있어.

게다가 std::vector에 더 많은 원소를 넣으려 할수록 차이는 점점 더 벌어지니까, 원소를 많이 넣으려 한다면 반드시 reserve를 해야겠지?

물론 정말로 원소를 몇 개나 넣을지 '돌려 봐야 아는' 경우에는 reserve를 쓰기 어렵겠지만, 그런 경우는 꽤 드물고 보통 그런 std::vector에 원소를 엄청 많이 넣는 경우는 더더욱 드물어.

reserve를 쓸 수 있는 곳에만 열심히 써줘도 프로그램의 성능을 큰 폭으로 개선시킬 수 있다는 거지.

B. 맨 앞의 원소를 여러 번 삭제해야 한다면 std::deque나 std::queue를 써라

가끔 알고리즘을 구현하다 보면 FIFO, queue형 자료구조를 써야 할 때가 있는데 그런 경우라면 std::deque를 쓰는 게 좋아.

std::deque는 std::vector와 달리 꼭 연속된 메모리를 사용할 필요가 없고, 앞의 원소를 삭제한다고 해서 뒤 원소를 당겨오거나 하는 작업이 없는 좀 복잡하고 특이한 컨테이너야.

그래서 뒤로 넣고 앞으로 빼는 FIFO형 자료구조가 필요하다면 std::deque를 쓰는 게 훨씬 효율적이야.

참고로 std::queue는 정말 순수하게 queue로써의 기능 (FIFO)만 구현된 컨테이너인데, 얘도 한 단계 까보면 deque로 구현돼 있어.

필요에 따라 std::queue로 충분하다면 그걸 쓰고, 조금 더 기능이 필요하다면 std::deque를 쓰면 될 거 같아.

C. 원소 여러 개를 삭제해야 한다면 새로운 std::vector에 조건부 복사를 해라

std::vector를 순회하면서 원소를 하나하나 삭제하는 것보다, 삭제할 원소를 점찍어둔 뒤에 새로운 std::vector에다가 그 원소들만 빼고 복사하는 게 훨씬 안전하고 효율적이야.

4. 에서도 말했지만 std::vector에서 원소를 삭제하는 건 여러모로 별로라서, 어지간하면 std::vector가 강점을 가지는 순회를 최대한 활용하고 reserve로 삽입의 효율을 높이는 편이 성능 면으로나 안정성 면으로나 더 좋아.

최대한 짧게짧게 쓴다고 노력해봤는데 그래도 다 쓰고 나니 분량이 꽤 길어졌네.

그래도 써먹기 그리 어려운 내용은 아니니까, 한번씩 읽어보고 잘 활용하길 바라!