Content deleted Content added
Marked a dead citation link |
m Dating maintenance tags: {{Dead link}} |
||
Line 30:
== Growth factor ==
The growth factor for the dynamic array depends on several factors including a space-time trade-off and algorithms used in the memory allocator itself. For growth factor ''a'', the average time per insertion operation is {{citation needed span|text=about ''a''/(''a''−1), while the number of wasted cells is bounded above by (''a''−1)''n''|date=January 2018}}. If memory allocator uses a [[First fit algorithm|first-fit allocation]] algorithm, then growth factor values such as ''a''=2 can cause dynamic array expansion to run out of memory even though a significant amount of memory may still be available.<ref name=":0">{{Cite web|title = C++ STL vector: definition, growth factor, member functions|url = http://www.gahcep.com/cpp-internals-stl-vector-part-1/|access-date = 2015-08-05|archive-url = https://web.archive.org/web/20150806162750/http://www.gahcep.com/cpp-internals-stl-vector-part-1/|archive-date = 2015-08-06|url-status = dead}}</ref> There have been various discussions on ideal growth factor values, including proposals for the [[golden ratio]] as well as the value 1.5.<ref>{{Cite web|url = https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D|title = vector growth factor of 1.5|website = comp.lang.c++.moderated|publisher = Google Groups}}{{Dead link|
Below are growth factors used by several popular implementations:
| |||