Also, Rust's Vec has the correct size hinting API, so we can say Vec::reserve(N) meaning that we expect to put as many as N more things into this Vec soon, or Vec::reserve_exact(X) meaning that we expect to put no more than X more things into this Vec, ever
With this distinct hint, reserve(N) preserves the amortized growth. Say we have total capacity 30, currently there are 20 items in the Vec, and Vec::reserve(20). So the advise is that the Vec may soon have up to 40 items, we should grow it. But since we weren't promised that's as big as it'll get, we grow it by doubling - to total capacity 60 items. If this is a pattern, repeatedly reserving space for 20 items and then adding them, this grows 30 -> 60 -> 120 -> 240 and so on, amortized growth as advertised - and growth is avoided when we're only "reserving" capacity we already have anyway.
Several languages, including C++ only provide the Vec::reserve_exact(X) feature, but name it reserve. Any such "reservation" is also implicitly promising there won't be further growth, so for our example it grows 30 -> 40 -> 60 -> 80 -> 100 -> 120 -> 140 ... our amortized growth strategy was destroyed and our performance will be much worse than O(1). In such a language students get taught not to use the reservation API to signal what they know and so they lose out on performance optimisations better than O(1)
I first ran into this feature because I was wondering about the over-allocation problem, and I realised this is solving a different but also important problem.
With this distinct hint, reserve(N) preserves the amortized growth. Say we have total capacity 30, currently there are 20 items in the Vec, and Vec::reserve(20). So the advise is that the Vec may soon have up to 40 items, we should grow it. But since we weren't promised that's as big as it'll get, we grow it by doubling - to total capacity 60 items. If this is a pattern, repeatedly reserving space for 20 items and then adding them, this grows 30 -> 60 -> 120 -> 240 and so on, amortized growth as advertised - and growth is avoided when we're only "reserving" capacity we already have anyway.
Several languages, including C++ only provide the Vec::reserve_exact(X) feature, but name it reserve. Any such "reservation" is also implicitly promising there won't be further growth, so for our example it grows 30 -> 40 -> 60 -> 80 -> 100 -> 120 -> 140 ... our amortized growth strategy was destroyed and our performance will be much worse than O(1). In such a language students get taught not to use the reservation API to signal what they know and so they lose out on performance optimisations better than O(1)
I first ran into this feature because I was wondering about the over-allocation problem, and I realised this is solving a different but also important problem.