std::vector / std::stack / std::deque 의 속도 차이

여러 가지 문제를 풀다 보면 stack 자료구조를 이용해야 할 때가 많이 있습니다.

그런데 vector 도 마치 stack처럼 사용할 수 있는데 혹시 vector를 사용하면 안 될까 라는 생각에

vector를 사용해 보았는데 stack 보다 더 빠른 결과가 나왔습니다.

그래서 이번에는 c++ 의 여러 가지 자료구조들의 속도를 한번 측정해 보았습니다.

 

측정에 사용된 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <time.h>
using namespace std;

#define looper 1000000

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	clock_t start, end;
	double result;


	vector <int> v;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		v.push_back(i);
	}
	while (!v.empty()) {
		v.pop_back();
	}
	end = clock();
	result = (double)(end - start);
	cout << "vector : " << result << "\n";
	

	stack<int> stk;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		stk.push(i);
	}
	while (!stk.empty()) {
		stk.pop();
	}
	end = clock();
	result = (double)(end - start);
	cout << "default stack : " << result << "\n";


	stack<int, vector<int>> v_stk;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		v_stk.push(i);
	}
	while (!v_stk.empty()) {
		v_stk.pop();
	}
	end = clock();
	result = (double)(end - start);
	cout << "vector stack : " << result << "\n";


	deque<int> dqu;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		dqu.push_back(i);
	}
	while (!dqu.empty()) {
		dqu.pop_back();
	}
	end = clock();
	result = (double)(end - start);
	cout << "deque : " << result << "\n";


	return 0;
}

백만번씩 push pop 한 실행 결과입니다.

 

일단 vector 와 stack을 비교해보면 무려 1.2 초 가량 차이가 나는 것을 볼 수 있습니다.

왜 이런 결과가 나오는 것일까요?

보통 생각대로라면 vector 보다 stack 이 훨씬 단순한데 stack 이 더 빨라야 하는 것 아닐까요?

 

이 이유를 알려면 stack 에 대해 알고 있어야 합니다.

stack 은 사실 따로 stack이라는 내부 컨테이너가 있는 것이 아닙니다.

vector, deque, list container 같은 내부 컨테이너들을 그대로 사용하되 마치 stack처럼 동작하게 해 둔 것입니다.

그러니까 사실 stack을 선언하면 기본값으로 deque로 선언이 됩니다.

 

그래서 결과를 보시면 default stack과 deque의 시간 차이가 그렇게 크지 않습니다.

stack의 내부 컨테이너로 vector를 사용하게 되면 vector와 거의 비슷한 결과가 나옵니다.

 

그런데 같은 내부 컨테이너를 사용해도 그냥 vector와 vector stack , deque와 deque stack을 보면 stack 이 뭔가 조금 더 느립니다.

그래서 알고리즘 문제를 풀 때는 그냥 vector를 사용해서 푸는 게 훨씬 빠릅니다.

그러나 나중에 어떤 프로젝트에 참여하게 되시거나 프로그램을 만들게 될 때 vector를 사용하게 되면 사용 용도가 모호해지는 현상이 발생할 수 도 있으므로 vector stack을 사용하시는 것을 추천드립니다.

 

결론

1. 알고리즘 문제를 풀 때는 vector 가 제일 빠르다.

2. 그러나 대형 프로그램을 짤 때는 용도가 모호해질 수 있으므로 vector stack을 사용하자.