So I was writing a program where I need to prepend items. I know that an array is not the suitable data structure for this use case, and I should reach for a deque. Fine, but I was wondering to myself if there can be a "smarter" array that handles prepends. There are two ways to go about it:
Use a data structure that implements everything say O(log n), so no particular operation is slow, but nothing is fast either.
Add some runtime checks in the code for, say, array to detect (at runtime) if a common but inefficient access pattern is being used and special case itself for that.
Both these approaches have their issues, which is why standard libraries (Swift or elsewhere) don't try these tricks, and just let the user (programmer) explicitly specify what they want.
Then it occured to me, a rather simple observation - the compiler knows enough to make the choice!
This decision tree can become quite complicated if one wants to handle all sorts of cases (just like with other compiler optimizations), but at its core, it is a choice between 3 data structures:
- Arrays (usually, and also the default if the compiler can't deduce any predominant access pattern)
- Set (if the compiler detects the most common operation is checking for element existence)
- Deque (if the compiler detects frequent prepends)
Of course, the programmer still can tell the compiler what they want explicitly, but for folks who don't care, they can say just give me this (for lack of a better name) "List" and figure out for me please which underlying data structure that best matches the access patterns of the code that I'm about to write using it.
Since the thought is so simple, other people would've also had had this thought previously, but I don't recall having encountered a language which does this for me. I can see two reasons why: (a) doing this compiler based selection might get hairy real soon in general cases, and (b) the world works fine without this too.
I don't know enough to say about (a), but if (b) is the only reason then I'd push a bit more. The way things are is fine for me and other existing programmers, this isn't an issue in practice, but the situation could be improved for future programmers. I have learnt about arrays and sets and dequeues etc (and am quite happy to have learnt about them), but should it be necessary for all folks to learn about them to be able to program? No, right? They can, if they want to, but if the language can abstract this choice for them efficiently, it is one less roadblock for newcomers.
I wasn't sure where to post this, I hope adding the "discussion" tag is enough to indicate that I'm just trying to put this thought out there, not necessarily expecting this to translate into a pitch. Since what I'm proposing is a compile time choice (and not a runtime choice), it cannot be done at the Collections library level, which is why I didn't post it in that category.