Content deleted Content added
→Growth factor: Add a table entry for the growth factor in the SBCL implementation of Common Lisp |
StarfarerVI (talk | contribs) Unreal Engine has an interesting growth factor that's similar to Python, which I believe is valuable to note. |
||
| (7 intermediate revisions by 6 users not shown) | |||
Line 45:
|~1.125 (n + (n >> 3))
|-
|[[Microsoft Visual C++]] 2013<ref>{{Cite web|title = Dissecting the C++ STL Vector: Part 3 - Capacity & Size|url = https://hadibrais.wordpress.com/2013/11/15/dissecting-the-c-stl-vector-part-3-capacity/|website = Micromysteries|access-date = 2015-08-05|first = Hadi|last = Brais| date=15 November 2013 }}</ref>
|1.5 (3/2)
|-
Line 56:
|Facebook folly/FBVector<ref>{{Cite web|title = facebook/folly|url = https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md|website = GitHub|access-date = 2015-08-05}}</ref>
|1.5 (3/2)
|-
|[[Unreal Engine]] TArray<ref>{{Cite web |date=2025-02-26 |title=Nested TArrays in structs and memory |url=https://forums.unrealengine.com/t/nested-tarrays-in-structs-and-memory/2357416/3 |access-date=2025-05-26 |website=Epic Developer Community Forums |language=en}}</ref>
|~1.375 (n + ((3 * n) >> 3))
|-
|Rust Vec<ref>{{Cite web|title=rust-lang/rust|url=https://github.com/rust-lang/rust/blob/fd4b177aabb9749dfb562c48e47379cea81dc277/src/liballoc/raw_vec.rs#L443|access-date=2020-06-09|website=GitHub|language=en}}</ref>
Line 66 ⟶ 69:
|2
|-
|[[Steel Bank Common Lisp|SBCL]] ([[Common Lisp
|2
|-
|[[C Sharp (programming language)|C#]] ([[.NET]] 8) List
|2
|}
Line 97 ⟶ 103:
Bagwell (2002)<ref>{{Citation | title=Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays | first1=Phil | last1=Bagwell | year=2002 | publisher=EPFL | url=http://citeseer.ist.psu.edu/bagwell02fast.html}}</ref> presented the VList algorithm, which can be adapted to implement a dynamic array.
Naïve resizable arrays -- also called "the worst implementation" of resizable arrays -- keep the allocated size of the array exactly big enough for all the data it contains, perhaps by calling [[realloc]] for each and every item added to the array. Naïve resizable arrays are the simplest way of implementing a
Mike Lam.
[https://w3.cs.jmu.edu/lam2mo/cs240_2015_08/files/04-dyn_arrays.pdf "Dynamic Arrays"].
Line 116 ⟶ 122:
== Language support ==
[[C++]]'s [[Vector (C++)|<code>std::vector</code>]] and [[Rust (programming language)|Rust]]'s <code>std::vec::Vec</code> are implementations of dynamic arrays, as are the <code>ArrayList</code><ref>Javadoc on {{Javadoc:SE|java/util|ArrayList}}</ref> classes supplied with the [[Java (programming language)|Java]] API<ref name=Bloch>{{cite book | title= "Effective Java: Programming Language Guide" |last=Bloch| first=Joshua| publisher=Addison-Wesley | edition=third | isbn=978-0134685991| year=2018}}</ref>{{rp|236}} and the [[.NET Framework]].<ref>[https://msdn.microsoft.com/en-us/library/system.collections.arraylist ArrayList Class]</ref><ref name=Skeet>{{cite book |last=Skeet|first=Jon|title= C# in Depth |date=23 March 2019 |publisher= Manning |isbn= 978-1617294532}}</ref>{{rp|22}}
The generic <code>List<></code> class supplied with version 2.0 of the .NET Framework is also implemented with dynamic arrays. [[Smalltalk]]'s <code>OrderedCollection</code> is a dynamic array with dynamic start and end-index, making the removal of the first element also O(1).
Line 131 ⟶ 137:
[[Common Lisp]] provides a rudimentary support for resizable vectors by allowing to configure the built-in <code>array</code> type as ''adjustable'' and the ___location of insertion by the ''fill-pointer''.
== See also ==
* [[Stack (data structure)]]
* [[Queue (data structure)]]
== References ==
| |||