What is the best way to represent tree structure in memory as a cache?

Question

Hello all I have tree with nodes. The nodes are constructed by TCP API request response value. To make less requests I'd like to represent the tree in a cache structure, that each time when TCP request are about to be invoked it will check the cache first. What is the best way to do it? I mean the tree cache part, in my case I'm using Qt and C++.

Answer 1

You can use a std:map<TCPRequest, TCPResponse> to achieve this. Your request and response could be string in which case that might reduce to std:map<std::string, std::string>. if not, you would need to ensure that your TCPRequest class supports operator< to allow the map to be binary searched.

Your code might look something like

#include <map>

std::map<TCPRequest, TCPResponse> responseCache;
typedef std::map<TCPRequest, TCPResponse>::const_iterator cacheCIterator;

TCPRequest nextRequest;
cacheCIterator iter = responseCache.find(nextRequest);
if (iter != responseCache.end())
{
  return iter->second;  // found cached response
}
else
{
  // issue the request
  TCPResponse response = issueRequest(nextRequest);

  //save the response
  responseCache[nextRequest] = response;
  return response;
}  

You also need to consider cache expiry, unless your traffic is small enough that you can just cache all responses. At some point you want to erase() TCPResponse objects from the map, possibly by keeping a separate structure that tells you which response was least recently used (LRU).

With this in mind some kind of unique identifier (a monotonically-increasing int would work) could be used in your TCPResponse objects as a proxy to the full objects, allowing you to identify the cache and LRU responses using ints instead of the full class instances. You still need full TCPRequest comparison in order to ensure the cache works as desired, though.

Answer 2

You might want to consider a hash map in case the number of outstanding requests is large. See QHash in the QT library, or std::hash_map (depending on the flavor of the STL you are using).