On Tue, Aug 25, 2026 at 10:59 PM G. Branden Robinson <[email protected]> wrote: > > The bottom line is that sorting an associative array is computationally > expensive--in time, in storage requirements, or both--and not necessary > for a great many applications of that kind of data structure.
What procedure generates the order of keys that we see? One would think the most computationally cheap way to keep references to all the elements would be to simply add them to the end of a linked list as they're added to the associative array. However, the same set of keys will generate the same order of elements no matter the order that the elements were added to the associative array. If this were the numerical order of the generated hashes, that would make sense, but it would be very inefficient to iterate through every possible hash to find those that link to an existing key/value pair. Bash could potentially implement a -s "sorted" option for the declare builtin, allowing the user to dictate that expansions of *this particular* associative array be in lexicographic order of keys. That would at least be more granular than a shopt option. Additionally, the LC_ALL/LC_COLLATE that's set when that declare command executes could dictate the collation order in effect throughout the lifetime of this associative array. So, a given red-black tree or whatever could be maintained throughout that time, rather than requiring bash to sort the associative array each time it's expanded. If the user wants to change the collation order later, they could call 'declare -As assoc' with a different LC_ALL/LC_COLLATE set, and then the red-black tree would need to be regenerated. But that would just be bash handling an edge case, and if the programmer knows what they're doing, they can easily avoid this. Similarly, an existing associative array could be given the -s sorted attribute and have the data members used to implement the red-black tree set at that time and the tree generated. And the -s sorted attribute could be turned off, having all that stuff set to NULL and giving the default arbitrary expansion order again. There could be a shopt option dictating that all associative arrays be given the -s sorted attribute by default, but the collation order is still set at declaration time of each associative array.
