Would an array of pointers to structs of key-value pairs be better
here? It should be faster in the common cases even though it may mean
some wasted space and reallocs depending on how you decide to grow the
array. A linear search through an array for an index should be faster
than linked-list traversal. https://youtu.be/YQs6IC-vgmo (why every
std::vector implementation uses arrays, really it's true of analogues
in most non-functional langs).
Also bash itself makes it hard to use sparse arrays efficiently regardless
of the implementation. In the case of lists, one usually wants to address
elements by ordinal position, but both the index in `arr[index]` and the
offset in `${arr[@]:offset:length}` don't allow it, which means random
insertion requires a linear search despite being linked-lists. That also
makes the "length" inconsistent with everything else that looks at the
value of the index, though at least length does what I really wish
offset did.
On top of that, ${!arr[@]:offset:len} doesn't even work. None of the
parameter expansions work with ${!arr[@]}, so to calculate an ordinal
index, a second array containing the indexes of the first is needed. Plus,
pre-existing items are overwritten on assignment, so insertion means
having to save and restore all the indexes and values at least in a
region being inserted to, which means more index calculation.
