Anonymous user
Talk:VList: Difference between revisions
→Some problems
Line 29:
::::: If your language provides higher level arrays and such, then all you need is a list, of course a data structure like VList would not be something you care -- but then you don't really worry about realloc either, do you? VList is a specifically low level construct, it ''is'' a way of doing memory management yourself. The sublist mentioned in the task is a use of the persistent pointer property: after you take an array slice, pushing more objects into the original list would not affect the validity of the slice, even though there's no further bookkeeping than just a pointer and an offset. --[[User:Ledrug|Ledrug]] 15:53, 13 September 2011 (UTC
:::::: Ok... perhaps this "languages with high level arrays do not need this" concept should be included in the task description? Meanwhile, to clone the array you need to copy the data from the first (biggest) block of data, which on average will contain c*n elements, where c is a constant (perhaps 0.25) and n is the length of the array. This means that that operation needs O(n) time. --[[User:Rdm|Rdm]] 16:25, 13 September 2011 (UTC)
::::::: Hmm? If you want to make a reference to a slice of the array, just copy the pointer and set a new offset, which is O(1). If you need to copy the content, then every block that's not empty should be copied, which involves all n elements that's currently filled. The point of taking a slice reference is to avoid this copying. --[[User:Ledrug|Ledrug]] 18:26, 13 September 2011 (UTC)
| |||