어느 게임 개발자의 기록

STL에선 벡터, 리스트, 맵, 셋, 해시 맵 등 다양한 자료구조를 제공해준다. 

그 중에서 벡터와 리스트는 자주 비교되는 자료구조이다. 두 자료구조의 차이를 알아보자.

std::vector

std;:vector는 배열 기반의 자료구조이다. 배열 기반인 만큼 모든 데이터가 메모리 상에 연속적으로 위치한다.

벡터의 특징은 대부분 메모리에 연속적으로 위치한다는 특성에서 시작된다.

먼저, 벡터는 임의 접근(random access)이 가능하다. 임의 접근이란 쉽게 말해서 원하는 원소에 바로 접근하는 것이다.

std::vector<int> Arr;

for(int i = 0; i < 10; i++)
{
    Arr.push_back(i);
}

위 코드와 같이 Arr이라는 벡터에 10개의 원소를 삽입했다고 해보자.

이 때, 5번째의 원소에 접근하고 싶다면, Arr[4]와 같이 인덱스를 통해 접근할 수 있다. 

(인덱스는 0번부터 시작하므로 5번째 원소는 4번 인덱스에 위치하게 된다.)

왜 이런 접근이 가능할까? 원소가 위치하는 주소를 특정할 수 있기 때문이다.

배열은 선언되면, 배열의 시작점을 주소값으로 보유하게 된다.

1번 원소 = 시작주소

2번 원소 = 시작 주소 + 원소의 메모리 크기

3번 원소 = (시작 주소 + 원소의 메모리 크기 * 2)

모든 원소의 메모리 크기는 일정하기 때문에, 위와 같은 방식으로 원소의 위치를 특정할 수 있는 것이다.

인덱스가 0번부터 시작하는 이유도 이 때문이다.

시작 주소 + (인덱스 * 원소의 메모리 크기) 의 공식을 세우려면 인덱스가 0부터 시작해야 하기 때문이다.

이처럼 데이터가 메모리에 연속적으로 위치한다는 특성 덕분에, 높은 캐시적중률을 자랑하기도 한다.

(캐시 적중률을 모른다면 여기를 참고)

하지만, 메모리에 연속적으로 위치한다는 특성때문에 몇 가지 문제점도 발생한다.

먼저 원소의 삽입과 삭제에 있어서 추가적인 연산이 발생한다는 것이다.

특정 원소를 삭제하게 되면, 배열 안에 비어있는 공간이 발생하게 된다. 이 빈 공간을 메꾸지 않으면 해당 인덱스에 접근할 때 어떤 오류가 발생할지 예측할 수 없으며 메모리 연속적이라는 특성도 사라지게 된다.

이로 인해, 벡터는 중간의 데이터를 삭제할 경우 모든 원소를 앞으로 끌어오게 된다. 이 과정에서 추가적인 연산이 발생하게 된다. 중간에 데이터를 삽입할 때에도 마찬가지이다. 원소를 모두 뒤로 밀어내야 하기 때문에 추가적인 연산이 발생하게 된다.

원소의 개수가 많아질수록 삽입 삭제 연산이 무거워지고 오버헤드가 커질 것이다.

두 번째 문제는 데이터를 메모리에 연속적으로 위치하게 하기 위해서,메모리 공간을 미리 확보해야 한다는 것이다. 10개의 원소를 삽입하려면 원소의 크기 * 10만큼 메모리 공간이 존재해야 하며 그 만큼을 선점해야 한다.

그런데, 메모리 공간은 원소 10개의 크기만큼만 확보하였는데 11번째 원소가 삽입된다면 어떻게 될까?

일반적인 배열의 경우엔 아예 불가능한 연산이지만, 벡터는 새롭게 메모리 공간을 동적으로 할당한 뒤 기존의 데이터를 모두 옮기고 기존의 메모리 영역을 해제하는 방식으로 해결한다. 즉, 기존에 할당한 메모리 공간보다 더 큰 공간을 필요로 하게 되면 메모리 할당 -> 데이터 복사 -> 메모리 해제의 과정을 거치므로 아주 커다란 오버헤드가 발생하게 된다.

이를 해결하기 위해선 어떻게 해야할까? 메모리 크기를 충분히 크게 할당해놓는 것이다. 벡터엔 reserve라는 멤버함수가 존재한다. 이 reserve를 통해 미리 충분한 크기의 메모리를 할당한 뒤에 그 범위 안에서 사용하게 되면, reserve를 호출할 때 메모리 할당 -> 데이터 복사 -> 메모리 해제의 연산을 1번 실행하고 이후에는 추가적으로 실행되지 않는다.

(할당해놓은 범위를 넘어서지 않는다는 조건 하에)

하지만, 메모리를 너무 많은 크기로 할당해놓게 되면 메모리 내부 단편화가 발생하므로 어느 정도의 메모리가 필요한지 미리 예측해놓고 필요한 만큼만 할당하는 것이 중요하다.

벡터의 특징을 정리해보자.

핵심 : 데이터가 메모리에 연속적으로 위치한다.

장점 1 : 임의 접근이 가능하다.

장점 2 : 캐시 적중률이 매우 높다.

단점 1 : 삽입, 삭제에 추가적인 연산이 필요하다.

단점 2 : 동적 할당과 데이터 이동으로 인한 오버헤드를 줄이기 위해 메모리를 미리 할당해야 한다.

(사실 Reserve, Resize 등의 함수를 한 번만 호출하면 되기 때문에 단점이라고 하기 애매하긴 하다.) 

std::list

std::list는 포인터 기반의 자료구조이다.

백터는 미리 메모리를 할당해 놓고, 그 안에서 순차적으로 데이터를 저장하는 반면 list는 새로운 원소가 추가될 때마다 새롭게 동적 할당을 하여 포인터로 이전의 원소와 연결하는 과정으로 데이터를 저장하게 된다.

이러한 특성 때문에, list는 데이터의 삽입과 삭제가 간단하다.

 새로운 원소를 추가하게 되면, 메모리를 동적으로 할당한 뒤에 포인터만 연결하는 과정을 거치면 되기 때문에, 원소가 어느 위치에 삽입되더라도 데이터를 뒤로 밀거나 앞으로 당기는 등의 추가적인 연산이 필요하지 않게 된다.

또한, 원소가 추가되는 만큼만 동적으로 할당하기 때문에 벡터처럼 미리 메모리를 할당해놓을 필요가 없고, 메모리 내부 단편화 또한 발생하지 않는다.

하지만, 원소가 추가될 때마다 계속 동적 할당을 실행하기 때문에 원소의 삽입 자체가 벡터에 비해 낮은 성능을 보이게 된다. 또한, 데이터가 메모리에 연속적으로 위치하지 않기 때문에 캐시 적중률 또한 매우 낮은 편이다. 

그 뿐만이 아니라, 포인터로 연결되어 있다는 특성 때문에 특정 원소의 주소값을 바로 유추할 수가 없어 임의 접근이 불가능하다. 첫 번째 원소부터 포인터를 타고 가며 접근하는 순차 접근만 가능하다.

리스트의 특징을 정리해보자.

핵심 : 데이터가 메모리에 연속적으로 위치하지 않고, 포인터를 이용해 논리적으로 연결되어 있다. 

장점 1 : 삽입, 삭제가 간단하다.

장점 2 : 메모리를 미리 할당할 필요가 없다. 

단점 1 : 임의 접근이 불가능하다.

단점 2 : 원소가 삽입될 때마다 동적 할당의 오버헤드가 발생한다.

단점 3 : 캐시 적중률이 매우 낮다.

삽입 삭제는 list가 vector보다 더 유리할까?

삽입, 삭제 연산을 빅오 표기법으로 표현하면 std::vector의 시간 복잡도는 O(n)이며, std::list의 시간 복잡도는 O(1)이다. 이 때문에, 리스트의 장점을 인터넷에서 찾아보면 삽입 삭제가 빠르다는 말이 항상 나온다.

하지만, 실제로는 그렇다고 단정지을 수는 없다. 

std::vector가 std::list에 비해 삽입 삭제가 느리다고 말하는 이유는 std::vector에선 데이터를 삽입, 삭제할 때 데이터를 뒤로 밀거나 앞으로 당기는 추가적인 연산이 필요하고, std::list에선 그러한 과정이 필요하지 않기 때문이다.

하지만 생각해보면 std::list는 데이터를 삽입, 삭제할 때 메모리를 할당하거나 해제하는 과정이 필요하다.

즉, std::list에서도 삽입, 삭제 시에 포인터만 끊고 연결하는 것이 아니라 메모리의 할당과 해제라는 추가적인 연산이 필요하다는 것이다.

그러므로 std::vector와 std::list의 삽입 삭제의 연산 속도를 비교하려면 원소를 앞으로 당기거나 뒤로 미는 연산 속도와 동적 할당, 메모리 해제의 속도를 비교해야 하는 것이다. 

또한, 시간 복잡도는 항상 최악의 경우만을 가정하지만, 실무에선 최악의 경우만 발생하는 것이 아니기 때문이다.

최선의 경우만 발생하는 로직에서도 과연 list가 vector보다 유리할까?

이를 직접 비교해보도록 하겠다.

#include <vector>
#include <list>
#include <iostream>
#include <chrono>

int main()
{
	std::vector<int> Vector;
	Vector.reserve(1000);

	std::list<int> List;
	
	{
		std::chrono::system_clock::time_point InsertStart = std::chrono::system_clock::now();

		for (int i = 0; i < 1000; i++)
		{
			Vector.insert(Vector.begin(), i);
		}

		std::chrono::system_clock::time_point InsertEnd = std::chrono::system_clock::now();
		std::chrono::nanoseconds VectorInsertDuration = std::chrono::duration_cast<std::chrono::nanoseconds>(InsertEnd - InsertStart);

		std::cout << "VectorInsertDuration : " << VectorInsertDuration << std::endl;

		std::chrono::system_clock::time_point EraseStart = std::chrono::system_clock::now();

		for (int i = 0; i < 1000; i++)
		{
			Vector.erase(Vector.begin());
		}

		std::chrono::system_clock::time_point EraseEnd = std::chrono::system_clock::now();
		std::chrono::nanoseconds VectorEraseDuration = std::chrono::duration_cast<std::chrono::nanoseconds>(EraseEnd - EraseStart);

		std::cout << "VectorEraseDuration : " << VectorEraseDuration << std::endl;
	}

	{
		std::chrono::system_clock::time_point InsertStart = std::chrono::system_clock::now();

		for (int i = 0; i < 1000; i++)
		{
			List.insert(List.begin(), i);
		}

		std::chrono::system_clock::time_point InsertEnd = std::chrono::system_clock::now();
		std::chrono::nanoseconds ListInsertDuration = std::chrono::duration_cast<std::chrono::nanoseconds>(InsertEnd - InsertStart);

		std::cout << "ListInsertDuration : " << ListInsertDuration << std::endl;

		std::chrono::system_clock::time_point EraseStart = std::chrono::system_clock::now();

		for (int i = 0; i < 1000; i++)
		{
			List.erase(List.begin());
		}

		std::chrono::system_clock::time_point EraseEnd = std::chrono::system_clock::now();
		std::chrono::nanoseconds ListEraseDuration = std::chrono::duration_cast<std::chrono::nanoseconds>(EraseEnd - EraseStart);

		std::cout << "ListEraseDuration : " << ListEraseDuration << std::endl;
	}
}

위는 1000개의 원소를 삽입, 삭제하는 속도를 비교하는 코드이다.

벡터에서 최악의 경우를 확인하기 위해 가장 앞에 원소를 삽입, 삭제하도록 하였다.

삽입,삭제 속도만을 비교하기 위해 reserve는 미리 해주었다.

1000개의 원소에 대한 결과는 아래와 같다.

최악의 경우임에도 불구하고 vector가 list에 비해 속도가 앞서는 것을 볼 수 있다.

10000개의 원소에 대해서도 체크해보자.

10000개로 원소가 늘어나니 list가 두 배 이상 앞서는 것을 볼 수 있다.

하지만, 벡터의 삽입 삭제를 맨 뒤에서 하도록 하면 어떨까?

위는 1000개의 원소에 대한 것이고, 아래는 10000개의 원소에 대한 것이다.

최선의 경우엔 벡터가 list보다 압도적으로 빠른 것을 알 수 있다.

원소의 개수가 많아질수록 최악의 경우엔 삽입, 삭제가 list가 훨씬 유리하다고 볼 수 있지만 최선의 경우엔 list가 vector보다 훨씬 빠른 것을 알 수 있다. 즉, 삽입 삭제가 list가 vector보다 항상 유리하냐고 한다면 답은 아니라는 것이다.

특정 로직에 사용할 자료구조를 선택할 때, 삽입 삭제가 자주 발생한다는 이유로 list를 선택하는 것은 정답이 아니다. 

현재 내가 구현하고 있는 로직이 어느 위치에서 삽입, 삭제가 자주 발생하는지 혹은 원소의 개수는 어느정도인지 파악한 뒤에 사용하는 것이 중요하다. 

또한 캐시 적중률의 차이로 순회의 경우 벡터가 압도적으로 빠르기 때문에, 삽입, 삭제 여부만 판단하는 것이 아니라 순회의 속도도 고려해야 한다. 아래는 10000개 원소의 순회 속도이다.

벡터 vs 리스트

두 자료구조의 차이를 표로 정리해보겠다.