Re: Quasi-Random Dynamic Array
On 2008-11-18 19:53, Giovanni Santostefano wrote:
Hi,
I'm Giovanni Santostefano.
I've written a paper on quasi-random dynamic arrays.
I want to share with us becaus I've seen on Exceptional C++ the
structure of vectors and I think allocate (during an extension) a new
array and copy the datas from the elder can be bad in certain
situations.
The idea behind my system (my system... but don't know if someone
created before me) is to build a list of arrays.
You can download the paper here
http://digilander.libero.it/blizzard.3dDevelop/dinarray.pdf
I'm not quite sure that I see the point, since we already have lost the
advantage of contiguous memory, why add the extra cost of O(n) for a
lookup. By using an array of pointers to the elements you retain the
O(1) lookup and inserts are very cheap since you only have top copy
pointers when the array needs to reallocate.
The only advantage I can see your solution having is slightly better
cache locality. If you make the subarrays large enough this might be a
win if you often iterate over the elements, but if you primarily do
random lookups there's no use.
You might also want to look at std::deque, just like your solution it
provides good performance for inserts at the front and back, but worse
for insertions in the middle, O(n) I think. I should note that the
performance for an array of pointers will also be O(n) for inserts in
the middle, but no objects will be copied/assigned and will be faster
for everything but really small classes/built-in types.
--
Erik Wikstr??m
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]