Coxie   2년 전

vector<vector<int>> v(100000);

이런 식으로 하는게 가장 효과적인가요?

vector가 1차원 배열로 구현 되어 있다고 한다면,

push_back을 계속 하다 보면 언젠가는 다 꽉찰테고, 

그려면 확장하기 위해서 시간을 들여야 할텐데,

그렇다면 차라리 linkedlist로 하는게 더 빠르지 않나요?

djm03178   2년 전

확장을 매 원소마다 하는 게 아니라 일정 크기를 잡아놓고 초과하려 할 때 한 번에 확 늘리는 식이라 그에 대한 오버헤드는 작다고 봅니다. 링크드 리스트가 오히려 포인터로 계속 관리를 해야 하기에 더 느리고 공간을 많이 먹지 않을까 싶네요.

chogahui05   2년 전

흐음.. ArrayList와 같은 동적 배열은

grow rate라는 게 있어서요. 예를 들어서 기존에 1000이라는 공간이 할당되어 있을 때

grow rate가 1.5라면 1500으로 확장되고요.

2라면 2000으로 확장되죠.


아마 걱정하는 부분은 동적 배열에서 add 연산 한 번 수행할 때 마다 드는 시간이 O(n)이 되지 않겠느냐.. 인 거 같은데요.

초과할 때마다 공간이 하나씩 늘게 하면 그럴 수도 있겠다만..

내부적으로 그러지 않으니까 너무 걱정 안 하셔도 되고요.


List가 효과적인 경우에는 (더블 링크드 리스트)

중간에 있는 원소를 삭제하거나, 중간에 원소를 추가해야 할 때가 있겠네요.

댓글을 작성하려면 로그인해야 합니다.