> What unsafe APIs would you like to see?
Well, here’s a simple example I’ve wrote above: “Some container that keeps some items + a linked list to track and evict the least recently used item from that container”.
You know, LRU caches are everywhere. I remember in C++, I recently wrote something similar in three completely unrelated projects. Well, a linked list alone isn’t usually enough, but a linked list + unordered map that maps elements to list iterators do the job very well. To update the LRU order, I query the hashmap and get a list position, then I move that element to the list’s tail. And when I need to evict an element, I grab the list’s head and evict those.
Note the following good things about this C++ solution:
(1) All those operations (hashmap lookup, linked list reorder, linked list remove head) are O(1), i.e. I can have millions items in my cache, and still update my LRU order for practically no cost (a few pointer writes).
(2) I didn’t wrote much code, only creatively combined what was already here in the C++ standard library.
Now Rust.
The safety means pointers to list nodes aren’t part of the list’s API.
And without raw pointers, linked lists are nearly useless, because we can’t split or reorder them efficiently. If you’ll read the documentation for LinkedList<T>::split_off, you’ll find the complexity is O(n), while for most other languages, linked lists are famous for being able to do that for O(1).
I’m not sure any efficient linked list API is possible within Rust memory management model, safe or unsafe.