On 9/26/16, Dan Douglas <orm...@gmail.com> wrote: > 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. >
friendly reminder that trees exist --- xoxo iza
