| Juha Nieminen <nospam@thanks.invalid>: Mar 17 06:10AM > Today someone in another forum told me, that some vector<>-impmemen- > tations grow the capacity in powers of two. I couldn't believe that > because it appeared to me as too much bloat. Growing the capacity in powers of two simply means that the growth factor is 2. I haven't actually checked the math, but I believe that the factor of 2 is used because of the standard requirement that push_back() must be amortized-constant-time, and I think that doesn't work with any factor less than 2 (although, as said, I haven't checked the math). It can be thought of like this: For each time a reallocation happens, which incurs an O(n) copying operation, you need an additional n O(1) operations to compensate (ie. keep the overall insertion time at O(1)). This can only work if the growth factor is 2. |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Mar 17 08:03AM +0100 On 17.03.2021 07:10, Juha Nieminen wrote: > must be amortized-constant-time, and I think that doesn't work > with any factor less than 2 (although, as said, I haven't checked > the math). With an initial size m and buffer increase factor C the work in copying from old to new buffers is 1m + Cm + C²m + C³m ... + Cʳm = m(1 + C + C²m + C³m ... + Cʳm) = m(Cʳ⁺¹-1)/(C-1) where r, the number of buffer increases, is the floor of the C-logarithm of current size n, so that Cʳ is O(n) regardless of the value of C. A simple way to understand the formula (which I used to write it now) is that e.g. 10³ - 1 = 999 = 9×(111) = 9×(10² + 10 + 1), so. > which incurs an O(n) copying operation, you need an additional n > O(1) operations to compensate (ie. keep the overall insertion time > at O(1)). This can only work if the growth factor is 2. It works for any growth factor ≥1, but the smaller it is the more time is spent on buffer reallocations, and perhaps the more fragmented memory becomes, while saving a bit on buffer size. - Alf |
| Paavo Helde <myfirstname@osa.pri.ee>: Mar 17 05:23PM +0200 16.03.2021 19:31 Bonita Montero kirjutas: > I expected since I so far assumed that growing the capacity efficiently > is the duty of the programmer and growing the vector with such hops is > really bloat for me. It cannot be left to the programmer because otherwise push_back() and emplace_back() would not have amortized constant complexity, as mandated by the standard. The exact factor (1.5 or 2) depends on the desired memory/speed balance. Nowadays memory is plenty, so newer compilers like clang prefer a larger factor. MSVC has most probably kept legacy factor 1.5 from some time in the past where memory tended to be more scarce. Just found this blog post about strings which discusses the same thing among others: https://shaharmike.com/cpp/std-string/ |
| olcott <NoOne@NoWhere.com>: Mar 15 09:09AM -0500 On 3/15/2021 8:38 AM, Andy Walker wrote: > restrict themselves to one posting per day. That would give us about > a dozen articles per day as light relief, rather than getting on for > 100 [which means I have to zap lots of them unread]. Any bloody idiot can continue to parrot: You are wrong, you are wrong, I know that you are wrong because I really really believe that you are wrong. I dare you or anyone else to find a single significant error (that changes the outcome) in any of this: http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment