Implementing a cache

[Lodovico Giaretta via Digitalmars-d-learn]

On Saturday, 2 July 2016 at 12:10:28 UTC, qznc wrote:
> I want to implement some caching for HTTP GET requests. 
> Basically a map of URL to content. A cache needs some 
> additional meta data (size, age, etc).
>
> There seem to be two basic data structures available: 
> Associative array (AA) or red black tree (RBT).
>
> With AA cache eviction is inefficient. It requires to sort the 
> keys of the AA with respect to a field in the value. Stack 
> overflow says "use RBT instead" [0].
>
> With RBT retrieving something is inefficient. To get an entry, 
> we need to create an fake entry with the key and get a range of 
> entries 'equal' to the fake one? Or can I exploit some "find on 
> sorted range" algorithm somewhere?
>
> Alternatively, any better idea to implement the cache? I guess 
> there is no off-the-shelf/dub solution.
>
> [0] 
> https://stackoverflow.com/questions/10060625/how-to-sort-associative-arrays

If I understand correctly, you want fast access based on the URL, 
but also fast access based on the age (to evict old entries)? If 
that's the case, you need some very complex structure (I have 
some ideas in mind based on a pair of indexes, but they require 
much effort).

Instead, if you just need an ordered associative array, like 
C++'s std::map, it should be possible to create one copying much 
of the code from the std RedBlackTree (as a side note, having a 
TreeMap in std.container would be a Good Thing(tm)).