std::vector를 stack처럼 사용하기

std::vector를 stack처럼 사용하기

std::vector 소개

동적 할당 메모리를 직접 관리하는 것보다 std::vector를 사용하는 것이 훨씬 편하다고 말씀드린 적 있다.

이번에는 std::vector의 사용법을 조금 더 살펴보고 스택처럼 사용하는 방법을 배워보자.

---

Length vs. Capacity

 

정수형 vector를 하나 선언했다.

std::vector<int> v{ 1,2,3 }; 이렇게 해주는 것은

int *v_ptr = new int[3]{1, 2, 3}; ← 과 비슷하다

동일하지는 않다.

vector에 대해서 얘기를 하기 전에 미리 알아두어야 할 게 있다.

 

길이만 기억하는 내장 배열이나 std::array와 다르게

std::vector에서는 size와 capacity 두 가지 속성이 있다.

capacity는 용량을 뜻한다.

사이즈와 용량이 어떻게 다른 개념인가? 생각할 수 있다.

 

지난번 포스팅에서 스택과 힙에 대해서 말씀드렸는데

Heap 같은 경우는 메모리 공간 잡아오는 것을 결정하는데 꽤 오래 걸린다.

꽤 오래 걸린다고 해도 컴퓨터가 하는 거니까 엄청 빠르긴 하다.

하지만 큰 프로그램을 만들 때에는 영향을 미칠 수 있는 수준이다.

Heap 에다가 메모리 주세요라고 요청해서 new와 delete하는 것은 느리니까 많이 안 쓰는 것이 좋다.

 

그런데 vector 같은 경우는 내부적으로 new, delete을 호출하면서

데이터 담을 공간을 만들기도 하고, 반납하기도 하고, delete으로 지우기도 한다.

vector를 잘 사용하는 방법은

내부에서 이루어지는 new와 delete이 "어떻게 하면 적게 호출될 것인가"를 생각하면서 쓰는 것이다.

그냥 모르고 써도 작은 프로그래밍을 할 때에는 문제가 없다.

하지만 크고 복잡한 프로그램 만들 때는 알아두는 것이 매우 중요하다.

 

그래서 capacity는 뭐냐면

실제로 코드 내부에서는 capacity 개수만큼 메모리를 가지고 있다.

그런데 size는 그중에서 몇 개만 사용을 한다 이런 의미로 보면 된다.

capacity는 메모리에 할당된 용량의 크기이다.

 

쉽게 이해할 있도록 for each를 이용한 간단한 예제를 보자.

 

이때 v의 size를 출력을 해보자

 

3개밖에 없으니까 3이 나온다.

size에 맞춰서 for each 문에서 도는 것이라고 생각하면 된다.

 

이번에는 resize를 해보자.

 

10개 정도로 크게 잡아보고 capacity도 출력을 해보자.

출력된 것을 보니까 뒤에 0이 많이 붙어있다.

그리고 출력이 될 때 10개가 출력이 되었다.

size도 10, capacity도 10이 나왔다. 두 개가 동일하다.

이런 경우가 한 가지 있고

---

Length vs. Capacity

이번에는 v.resize를 더 작은 값으로 해보자.

3개에서 2개로 줄이는 거다

한번 출력해보면

 

출력된 걸 보니까 1과 2가 출력되었다.

뒤에 3은 출력이 안되었다.

그런데 size는 2인데 capacity는 여전히 3이다

용량은 그냥 3을 유지를 하고 출력을 할 때만 2를 출력을 한 것이다.

 

여기서 한 가지 더, 강제로 3이 출력되게 해 보자.

 

이렇게 하고 빌드해보면 

 

런타임 에러 난다.

그리고 .at 을 이용해서 다시 출력해보자

 

이렇게하면 또한 런타임 에러가 난다

강제로 int의 포인터를 가져와보자

 

int* ptr = v.data(); 이렇게 하면 포인터를 가져올 수 있다.

그다음 출력해보면 3이 나온다.

 

지금 뭘 한 거냐면 얘가 마지막에 하나 더 갖고 있는데 없는 척한 거다.

그걸 억지로 가져온 거다.

 

이게 왜 중요하냐면 resize를 할 때 원래 동적메모리를 직접 할당하면

vector v가 지금  세 개짜리 int를 갖고 있을 것이다.

이 세 개짜리를 두 개로 줄일 때

OS한테 "난 세 개 중에 두 개 만 쓸래. 그러니까 일단 두 개짜리 메모리를 먼저 줘"라고 해서

두 개를 받아놓고

그다음에 원래 세 개 였으니까 세개 중에 두 개를 새로 받은 메모리로 복사를 한다.

그리고 원래 갖고 있던 세 개짜리 메모리는 delete으로 지워버리면

결과적으로 두 개 짜리 메모리 1, 2 가 저장되어있는 두 칸짜리 메모리를 깔끔하게 갖게 된다.

 

그런데 vector는 설계가 될 때 속도를 좀 높이는 쪽으로 좀 더 강조가 된 것이다.

그래서 더 작은 쪽으로 resize를 할 때

메모리를 반납하고 지우는 것을 하면 느려지니까 그걸 하지 않고

 

메모리는 그냥 갖고 있고 그냥 슬쩍 아 나는 두 개밖에 없어요라고 여기서 능청을 떠는 거다.

그리고 v.size 와 v.capacity를 찍어보면 이게 확실히 드러난다.

size는 두 개인데 capacity는 3인 거다

실제 갖고 있는 메모리 하고 사이즈가 다르다는 것 기억하기!

 

지금은 for-each를 사용해서 많이들 출력을 하는데

 

예전에는 이런 식으로 출력을 많이 했다.

 

v.size 이게 현재 사이즈로 막아버리는 거다. 1, 2까지밖에 안된다고

resize를 했더니 뒤에 0으로 자동으로 채워버리는 것은 확인을 했다.

 

이번에는 capacity 강제로 키워보자.

 

.reserve 라는게 있다.

이거는 메모리의 용량을 미리 확보해놓겠다는 의미다

아까 resize를 했을 때는 뒤에 0이 나왔는데

지금은 1 2 3 만 나오고 0이 안 붙었다.

사이즈를 찍어봐도 3만 나온다.

그런데 capacity를 찍어보니까 1024 reserve 해놓은 거로 나온다.

 

그럼 reserve를 왜 하는 걸까?

뒤에 원소가 추가가 될 때 reserve된 공간이 많이 남아있으면

새로 메모리를 바꿔오고 교체하는 작업을 하지 않는다.

그래서 훨씬 빠르다.

 

지금 상황에서는 속도를 재면서 까지 비교할 상황은 아니지만

나중에 속도를 재 볼일이 있어서 재보면 확실히 차이가 난다.

new, delete을 부르는 게 느리기 때문에

size하고 capacity가 다르게 사용할 수 있는 구조를 가지고 있다고 알아두면 된다.

 

---

std::vector로 stack 동작

일단 위 예제에서 v를 stack으로 바꾸고 빈 stack으로 시작하겠다.

 

reserve를 해도 되고 안 해도 되지만 하면 확실히 속도 차이가 난다.

나중에 recursive function 재귀 호출을 할 때 스택 오버플로우가 나온다.

스택 오버플로우가 나는데 재귀 호출과 같은 알고리즘을 반드시 구현을 해야 한다.

그런 상황에는 vector를 stack으로 사용하는 방법이 있다.

그래서 위처럼 사용하는 게 아주 드문일은 아니다.

 

함수로 뺐다

stack을 입력받아서 출력하는 함수를 하나 만들었다.

stack이라는 게 접시처럼 위로 쭉쭉 쌓았다가

위에서부터 다시 뺀다고 말씀드렸다.

이런 것을 push 한다 pop 한다라고 부른다.

 

정리하자면

std::vector는 동적 배열이지만 stack처럼 동작할 수 있다.

이를 위해 다음 3가지 함수를 사용한다.

 

• push_back : 스택의 요소를 푸시한다.
• back() : 스택의 최상위 값을 반환한다.
• pop_back() : 스택에서 요소를 팝한다.

vector를 이용해서 push , pop을 할 때는 

 

보통 이런 식으로 이루어진다.

이때 내부적으로 어떤 일이 벌어지는지를 확인하기 위해서

print 해보는 코드를 넣어보자.

 

3을 push 한 다음에 print를 하니까 3이 한 개 들어있고

5를 push 한 다음에 print 하니까 3 5가 되었고

7을 push 한 다음에 print 하니까 3 5 7이 되었다

그다음에 pop을 했더니 뒤에 있는 7이 빠지고 3 5만 남았다

pop을 한번 더 했더니 3만 남았고

그 다음에 pop을 한번 더 했더니 3 조차도 빠져버렸다.

이렇게 stack을 간단하게 구현을 해봤고

응용은 나중에 할 예정이다.

 

근데 왜 하필 stack을 vector로 구현을 하냐 

 

아까 말씀드렸듯이

vector에서 reserve를 하면 pushback을 할 때 capacity를 늘릴필요가 없다.

그러면 new와 delete을 호출할 필요가 없어서 효율이 더 좋다.

반대로 pop을 할 때는 capacity를 유지를 한 채로 pop을 해서

size만 줄어든 형태로 사용을 할 수가 있다. 효율이 높다.

 

단점은 reserve를 너무 크게 해 놓으면 capacity가 너무 커서 메모리가 낭비될 수 있다.

그런데 요즘 컴퓨터는 웬만한 경우에는 그 정도 가지고는 낭비가 된다고 보지 않는다.

물론 빅데이터를 다룬다거나 할 때는 고민을 할 수 있다.