Implementing a cache

[Steven Schveighoffer via Digitalmars-d-learn]

On 7/2/16 8:10 AM, 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?

Yes, it is annoying to have to deal with creating a fake element. In 
dcollections, I have a TreeMap wrapper which does this for you: 
https://github.com/schveiguy/dcollections/blob/master/dcollections/TreeMap.d#L881

We should probably add support for the searching functions that allows 
parameters other than full elements if the element supports comparison 
with that type.

In terms of using equalRange, it should be pretty efficient. If you are 
allowing duplicates, then it does 2 binary searches (one for the 
beginning node and one for the end). If no duplicates, one binary 
search, and the equalRange will be 0 or 1 element (depending on if the 
key is present).

> Or can I exploit some "find on sorted range" algorithm
> somewhere?

There is find on sorted range support in std.algorithm, but it must be a 
random-access range. RBTree range is not RA. What's wrong with the 
binary search support in the tree itself?

-Steve