將內存中的樹形結構表示爲緩存的最佳方式是什麼？

Question

全部你好 我有樹有節點。節點由TCP API請求響應值構建。 爲了減少請求的數量，我想在緩存結構中表示樹，每當TCP請求即將被調用時 它將首先檢查緩存。 做什麼是最好的方法？我的意思是樹緩存部分，在我的情況下，我正在使用Qt和C++。

Answer 1

您可以使用std:map<TCPRequest, TCPResponse>來實現此目的。您的請求和響應可能是字符串，在這種情況下可能會減少到std:map<std::string, std::string>。如果沒有，你需要確保你的TCPRequest類支持operator<允許二進制搜索地圖。

您的代碼可能看起來像

#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; 
} 

您還需要考慮高速緩存期滿，除非你的流量是足夠小，你可以緩存所有響應。在某些時候，您希望erase()TCPResponse來自地圖的對象，可能通過保留一個單獨的結構來告訴您哪個響應最近最少使用（LRU）。

考慮到這一點的某種唯一標識符（單調增加int會工作），可以在你的TCPResponse對象作爲代理的全對象使用，使您能夠識別高速緩存，並使用int小號LRU反應，而不是的全班實例。儘管如此，仍然需要完整的TCPRequest比較才能確保緩存工作正常。

Answer 2

如果未完成請求的數量很大，您可能需要考慮哈希映射。請參閱QT庫中的QHash或std :: hash_map（取決於您使用的STL的風格）。