The main fundamental data structure I find missing from Perl 5 is the "sorted associative array". I'd say "sorted hash" because it should act like a Perl hash except the keys are sorted, except that such are not implemented via a hash table; they are usually implemented via balanced trees.

Yes, there are various implementations of sorted hashes that have been bolted on to Perl 5. Many of them don't scale like a real balanced tree implementation would. The ones that scale well usually have a quite significant performance penalty constant applied to them (such as due to using tie or being file-based) and the rest usually have significant complications related to availability, convenience, flexibility, etc.

If there is one "best", efficient and convenient implementation of "sorted associative array" for Perl 5, then I'm not aware of it. This is likely my ignorance. I'd love to be pointed to a really good solution to this problem.

Complaining about this again reminded me of Judy. I even got excited when I saw Judy::HS mentioned as being keyed by arbitrary Perl strings. I have a good deal of appreciation for the Judy data structure and of respect for the author of the Judy module, so I figured there was a good chance that this was what I'd been hoping for. But Judy::HS values are restricted to being integers.

It seems a small step to go from "integer" to SV or even just to "reference" but a step perhaps better done in C (XS). I've put out an inquiry to the Judy.pm author regarding this.

Anyway, the times I have longed for a linked list in Perl 5, a sorted associative array would've been an acceptable solution (often better, in some ways). Perhaps such would scratch the Y (or Ys, if any) behind the original poster's X. :)