kukya님 갑자기 궁금한거 생각난게 있는데

[nyangdu..(210.118)]

vector가 random access 로 구현되있는데 범위 초과하면 다시 임의의 배수만큼 재할당해서 다시만드는데 이 재할당할때 배수를 결정하는 요인이 뭐에여?

그냥 고정값이에요?

[kukyakya(143.248)]

음 일단 random access가 가능한거랑 재할당이랑은 크게 상관은 없구욘

[kukyakya(143.248)]

push_back할 때 공간이 부족하면 재할당을 하고 기존 데이터를 옮기는데, 단순히 2n+1 크기로 재할당하는 경우가 젤 흔하지 싶은데

[kukyakya(143.248)]

저렇게 하면 기존에 할당했다가 해제한 공간이 재할당될 가능성이 없어서

[kukyakya(143.248)]

1.4 * n 을 쓰거나 하기도 함미다.

[씨푸로스트(59.3)]

이야 멋지다 갠지난다 갠지나

[nyangduck(210.118)]

아 그냥 2n +1 이에요??? 따른 알고리즘없이요?

[nyangduck(210.118)]

루트2네여

[nyangduck(210.118)]

근데 왜 2n+1로 하면 기존에 할당했다가 해제한공간이 재할당될 가능성이없는거에요? 메모리 해제해주면 그공간에 다시 메모리 할당될수도있지않아요? 힙에서 데이터 계속 쌓아올라가서 그런가

[kukyakya(143.248)]

음 메모리 공간을 0부터 +inf 까지로 무한하다고 보면요

[kukyakya(143.248)]

처음에 1개 할당했을떄 0이라고 치고

[kukyakya(143.248)]

2*n으로 재할당하면 2개의 공간이 필요하니까 [1,2]가 할당되고, 그 담엔 4개의 공간이 필요하니까 [3,6]이 할당되고 하다보면

[nyangduck(210.118)]

아.. 그러네여 절대로 재할당될수가 없겠네여 사라지는것보다 추가되서 다시할당해야하는 메모리영역이 커지니까요

[kukyakya(143.248)]

앞에 해제된 공간이 항상 2*n보다 작아서 메모리 할당이 뒤로만 쭉 진행되게 되는데, 이 때 2보다 작은 k값을 골라서 사용하면 적당한 횟수 이후에는 앞에 해제된 공간이 k*n보다 작아져서 할당을 앞에서 다시 할 수 있심여

[kukyakya(143.248)]

네 그렇죠

[nyangduck(210.118)]

근데 루트2도 마찬가지 아닌가요 그럼 어찌됫건 사라지는 사이즈보다 재할당해야하는 사이즈가 큰건 어쩔수없는데

[nyangduck(210.118)]

이게 배수만큼의 재할당 -> 값 복사-> 이전 영역 메모리해제 순으로 가는데 이게 재할당될때 무조껀 위쪽에 다시 쌓여야하는 구조인건 맞겠네요

[kukyakya(143.248)]

수학적으로 표현하면 f(n) = k * f(n-1)이 되는데, f(n) < sigma(f(i), i=1..n-2) 를 만족하는 i가 존재하는 k를 찾으면 돼요. 이게 k가 2보다 작으면 저런 i가 무조건 존재하는데, 예전에 얼로케이터 짤 때 참고했던 자료에 k에 따라서 몇번 재할당 후에 앞으로 돌아오는가 계산한 블로그 포스팅이 있었는데 지금 찾을라니까 어딨는지 기억이..

[nyangduck(210.118)]

나도 그래서 지금점화식 끄적이고있는데 수학 고자라서 식만써놓고 못푸는중 ㅠㅠ