list와 vector를 비교하면 보통 시간복잡도 표부터 나온다.

vector는 중간 삽입과 삭제가 O(n)이고, list는 O(1)이니 중간에 넣고 빼는 일이 많으면 list를 쓰라는 식이다.

근데 이 설명만으로 자료구조를 고르기에는 빠진 내용이 꽤 많다. 삽입할 위치는 어떻게 찾는지, 메모리는 어떻게 할당하는지, 순회할 때 cpu는 무엇을 읽어야 하는지까지 같이 봐야 한다.

C++의 list와 vector를 기준으로 쓰지만, 기본적으로는 양방향 링크드 리스트와 동적 배열의 비교다. vector<bool> 같은 특수화는 여기서 제외한다.

중간 삽입이 O(1)이라는 말

구분	vector	list
인덱스로 원소 접근	O(1)	O(n), 순회 필요
맨 뒤에 원소 하나 추가	분할상환 O(1), 재할당 시 O(n)	O(1)
맨 뒤 원소 삭제	O(1)	O(1)
중간에 원소 하나 삽입·삭제	O(n)	위치의 iterator가 있으면 O(1)

list의 중간 삽입이 O(1)인 건 삽입할 위치의 iterator를 이미 가지고 있을 때 얘기다. 해당 노드 앞뒤의 연결만 바꾸면 되니 원소 수에 비례해서 작업이 늘어나지 않는다. 삭제도 마찬가지다. cppreference의 insert와 erase 복잡도 설명도 위치를 넘겨받는 삽입·삭제 연산에 대한 것이다.

그럼 천 번째 원소 앞에 넣으려면?

vector는 인덱스로 바로 위치를 구할 수 있지만 list는 노드를 따라가면서 찾아야 한다. 값으로 찾는 경우에도 따로 검색 구조를 두지 않았다면 순회가 필요하다. 위치를 찾는 비용까지 넣으면 전체 작업은 O(n)이 될 수 있다.

그렇다고 이 전제만 고치면 비교가 끝나는 것도 아니다. 같은 O(1)이라고 해도 실제로 하는 일이 다르다.

메모리 할당

일반적인 list 구현은 각 원소를 별개의 노드로 할당한다. 추가할 때 노드 공간을 할당하고 원소를 생성한 뒤 연결을 붙인다. 삭제할 때는 연결을 끊고 원소를 소멸시킨 다음 노드 공간을 반환한다.

앞뒤 포인터 몇 개 바꾸는 건 간단하다. 근데 그 앞뒤에 메모리 할당과 해제가 붙는 거다.

힙 할당이 매번 시스템 콜로 이어지는 건 아니다. 이미 확보해 둔 공간에서 가져올 수도 있다. 윈도우의 힙도 확보한 페이지 안에서 메모리 블록을 관리하고 필요하면 페이지를 추가로 확보하는 식이다. 그래도 빈 블록을 찾고 관리하는 비용은 남는다. allocator에 따라서 동기화 비용이 붙을 수도 있다.

vector는 용량이 남아있으면 확보된 공간의 끝에 원소를 생성한다. 이때 컨테이너 저장 공간을 새로 할당할 필요는 없다. 물론 원소 자체가 내부적으로 동적할당을 하는 타입이면 그 비용은 별개다.

용량이 모자랄 때는 더 큰 공간을 할당하고 기존 원소를 이동하거나 복사해야 한다. 한 번의 작업은 비싸지만, 원소를 추가할 때마다 이 작업을 하는 건 아니다. 맨 뒤 삽입의 분할상환 O(1)은 이 비용을 여러 삽입에 나눠서 보는 얘기다.

list에 메모리 풀을 붙이면 노드 할당 비용을 줄일 수 있다. 그러니 할당 방식이 다른 컨테이너를 시간복잡도만 보고 같은 비용으로 생각하면 안 된다.

순회할 때의 메모리 접근

list의 노드에는 데이터 외에도 앞뒤 노드를 가리키는 포인터가 들어간다. 포인터가 8byte인 환경이라면 보통 두 포인터만으로 16byte가 붙는다. 여기에 패딩이나 allocator의 관리 정보가 추가될 수도 있다.

작은 정수 하나 넣자고 데이터보다 더 큰 공간을 쓰는 셈이다.

노드끼리 연속으로 붙어있다는 보장도 없다. 순회 순서대로 가까이 할당될 수도 있지만, 삽입과 삭제가 반복되면 다음 노드가 어디에 있을지는 모른다.

cpu가 다음 원소를 읽으려면 지금 노드에 들어있는 다음 포인터부터 읽어야 한다. 그 주소를 알아야 다음 노드로 갈 수 있으니 메모리 접근이 서로 의존하게 된다. 노드가 흩어져 있으면 캐시 라인에 같이 올라온 주변 공간도 순회에서 제대로 못 쓸 수 있다.

vector는 원소가 연속으로 붙어있다. 작은 원소를 순서대로 읽으면 한 캐시 라인에 들어온 여러 원소를 이어서 쓸 수 있고, 다음에 읽을 주소도 규칙적이다. 하드웨어가 미리 가져오기에도 유리하다.

그렇다고 무조건 캐시 히트가 난다는 얘기는 아니다. 데이터가 캐시보다 클 수도 있고 원소 크기나 접근 순서에 따라서 효과도 달라진다. vector 안에 포인터를 넣었다면 연속으로 붙어있는 건 포인터들이지, 그 포인터가 가리키는 객체들까지는 아니다.

순회가 많은 코드에서는 이런 차이가 꽤 중요하다. 시간복잡도는 둘 다 O(n)인데 실제로 cpu가 기다리는 시간은 다를 수 있기 때문이다.

vector의 비용을 줄이는 방법

미리 공간 확보하기

원소가 얼마나 들어올지 예상할 수 있다면 reserve()로 공간을 먼저 확보할 수 있다. 확보한 capacity를 넘기 전까지는 삽입 때문에 저장 공간을 다시 할당하지 않는다. cppreference의 reserve 설명에서 확인할 수 있는 보장은 여기까지다.

매번 원소를 하나 추가할 때마다 reserve(size() + 1)을 부르면 오히려 불필요한 재할당을 반복하게 될 수 있다. 대략 필요한 크기를 알고 있을 때 한 번 확보하는 쪽으로 써야 한다.

반복 작업이라면 vector를 매번 새로 만들고 버리기보다 clear()한 뒤 다시 쓰는 방법도 있다. 원소는 소멸하지만 capacity는 남으니 다음 작업에서 공간을 재사용할 수 있다. 여러 버퍼가 동시에 필요하면 풀로 관리할 수도 있지만, 재사용할 용량을 넘기는 경우의 할당까지 없어지는 건 아니다.

순서가 필요 없는 삭제

중간 원소를 지우면서 순서를 유지하려면 뒤의 원소들을 당겨야 한다.

근데 순서가 필요 없다면?

삭제할 자리에 맨 뒤 원소를 옮기고 pop_back()하면 된다. 흔히 swap and pop이라고 부르는 방식이다. 나머지 원소를 전부 당길 필요가 없어진다.

단, 삭제할 위치를 이미 알고 있어야 하고 원소의 교환·이동과 소멸 비용도 봐야 한다. 순서가 바뀌니 외부에서 원소의 인덱스를 저장하고 있다면 그 정보도 같이 고쳐줘야 한다.

정렬 상태가 언제 필요한지

항상 정렬된 상태가 필요해서 매번 중간에 삽입하는 경우라면, 그 상태가 정말 삽입 직후부터 필요한지 생각해볼 만하다.

데이터를 모은 다음 한 번 처리하는 구조라면 맨 뒤에 추가하고 처리 전에 std::sort를 하는 방식으로 바꿀 수 있다. 반복적인 원소 이동을 줄이는 방법이다.

반대로 삽입할 때마다 정렬된 결과로 검색하거나 처리해야 한다면 이렇게 바꿀 수 없다. 정렬 횟수와 데이터 크기도 봐야 하니 무조건 더 빠르다고 할 수는 없다.

여러 스레드에서 사용한다면

이건 vector만의 문제는 아니다. 여러 스레드가 같은 컨테이너를 읽기만 하는 상황과, 읽는 동안 다른 쪽에서 삽입·삭제하는 상황은 다르다. 접근한다고 자동으로 락이 걸리는 것도 아니다. 수정이 겹칠 수 있다면 사용하는 쪽에서 동기화를 맞춰야 한다. cppreference의 컨테이너 스레드 안전성 설명에도 서로 다른 원소의 수정처럼 별도로 허용하는 경우가 있으니 작업 종류를 구분해야 한다.

프레임이나 작업 단위로 데이터를 넘기는 구조라면 읽는 버퍼와 쓰는 버퍼를 나누는 방법을 생각할 수 있다. 한쪽에서 결과를 만드는 동안 다른 쪽은 완성된 데이터를 읽고, 작업이 끝나면 역할을 바꾸는 식이다.

근데 vector 두 개를 만들었다고 동기화 문제가 없어지지는 않는다. 완성된 버퍼를 공개하는 시점을 맞춰야 하고, 읽는 쪽이 다 읽기 전에는 그 버퍼를 다시 쓰면 안 된다. 더블 버퍼링은 접근 구조를 바꾸는 방법이지 그 자체로 락이 필요 없다는 보장은 아니다.

list를 쓸 이유

위치의 iterator를 계속 들고 있고 그 주변에서 삽입·삭제가 반복된다면 list의 장점이 살아난다. 기존 원소를 이동시키지 않고 연결을 바꿀 수 있고, 다른 원소의 iterator나 참조도 삽입 때문에 무효화되지 않는다. 삭제할 때는 삭제된 원소의 것만 무효화된다. splice로 노드를 옮기는 기능이 필요한 경우도 있다.

vector는 재할당이 일어나면 기존 원소의 포인터, 참조, iterator가 무효화된다. 재할당이 없어도 중간 삽입·삭제는 해당 위치 이후에 영향을 준다. 이게 코드의 요구사항에 맞는지도 봐야 한다.

순회와 끝 삽입이 주된 작업이고 원소를 옮기는 비용이 크지 않다면 vector부터 검토할 만하다. 반대로 원소의 주소를 유지해야 하거나 이동 비용이 크다면 얘기가 달라진다. 중간 삽입이 많다는 사실 하나보다, 위치를 어떻게 찾고 이후에 어떻게 사용하는지가 중요하다.

여기서 더 나아가 작은 데이터 집합을 검색할 때는 vector의 순차 검색이 unordered_map보다 빠를 수도 있다. 해시 계산과 메모리 접근 비용보다 연속된 작은 배열을 읽는 비용이 작을 수 있기 때문이다. 이것도 키 비교 비용과 원소 수에 따라 달라지는 얘기라 실제 사용할 데이터로 측정해봐야 한다.