What is a shadow array and how is it implemented? I came through the term while reading about compiler optimizations but I couldn't find any substantial reference about it.
3 Answers
When using arrays to implement dynamically resizable abstract data types, such as a List, Queue or Stack, the obvious problem that one encounters is that arrays are not themselves freely resized. At some point, then, if one adds enough items to an array, one will eventually run out of space.
The naive solution to this problem is to wait until the array being used runs out of space and then create a new larger array, copy all of the items from the old array into the new array, and the start using the new array.
A shadow array using implementation of an abstract data type is an alternative to this. Instead of waiting until the old array is full, a second, larger array is created after some threshold of fullness is passed on the array that's being used. Thereafter, as items are added to the old array, multiple items are copied from the old array to the shadow array, such that when the old array is full, all of it's items have already been copied to the new array.
The advantage of using a shadow array implementation instead of the naive "copy everything at the end" approach is that the time required by each add operation is much more consistent.
-
1This sounds better than my answer, do you have any source for your statements?:)– kmindiJul 18, 2014 at 11:43
-
I actually do! "Advanced Data Structures" By Peter Brass. Chapter 1, section 1.5, "Shadow Copies of Array-Based Structures" amzn.com/0521880378– jwrushJul 24, 2014 at 18:16
I think of it as a form of dynamic array.
The term shadow would referr to the underlying algorithms that try to resize it with good performance but are hidden behind an easy interface. (For example ArrayList in Java)