<p dir="auto">The standard way of representing an LRU is to have nodes be stored in a hashmap or binary search tree, with lookup-by-key, and in a linked-list which represents recency. This allows O(1) or O(logn) lookup/insert time, and constant time update/eviction with the recency list.</p>
<p dir="auto">The representation is usually something like:</p>
<div class="highlight highlight-source-c++ notranslate position-relative overflow-auto" dir="auto" data-snippet-clipboard-copy-content="struct LRU&lt;K,V&gt; {
    struct node&lt;K,V&gt; *tree_root;
    struct node&lt;K,V&gt; *recency_head, *recency_tail;
}
struct node&lt;K,V&gt; {
    K key;
    V value;
    struct node&lt;K,V&gt; *tree_parent, *tree_left, *tree_right;
    struct node&lt;K,V&gt; *recency_prev, *recency_next;
}"><pre class="notranslate"><span class="pl-k">struct</span> <span class="pl-en">LRU</span>&lt;K,V&gt; {
    <span class="pl-k">struct</span> <span class="pl-en">node</span>&lt;K,V&gt; *tree_root;
    <span class="pl-k">struct</span> <span class="pl-en">node</span>&lt;K,V&gt; *recency_head, *recency_tail;
}<span class="pl-ii"></span>
<span class="pl-k">struct</span> <span class="pl-en">node</span>&lt;K,V&gt; {
    K key;
    V value;
    <span class="pl-k">struct</span> <span class="pl-en">node</span>&lt;K,V&gt; *tree_parent, *tree_left, *tree_right;
    <span class="pl-k">struct</span> <span class="pl-en">node</span>&lt;K,V&gt; *recency_prev, *recency_next;
}<span class="pl-ii"></span></pre></div>
<p dir="auto">This is more difficult to represent in Rust. You could do it with <code class="notranslate">@mut</code> pointers, but we all know what would go wrong there, and also that would prevent you from sharing it between tasks. You could also do it with unsafe pointers. I suggest instead representing it as a vector, and replacing the pointers with indices into the vector.</p>
<p dir="auto">It would be really nice to have a very efficient, reusable implementation of this common pattern. It can be implemented as a hash table with an intrusive doubly linked list threaded through the entries.</p>
<p dir="auto">This is also how Python implements <code class="notranslate">OrderedDict</code> and Java implements <code class="notranslate">LinkedHashMap</code>.</p>