在C++中實現一個LRU緩存 - 編譯錯誤

Question

我需要在C++中實現一個LRU緩存。 我有這樣的代碼，我有問題，而編譯：

#include <iostream> 
#include <vector> 
#include <hash_map> 

using namespace std; 
using namespace stdext; 

template<class K, class T> 
struct LRUCacheEntry 
{ 
    K key; 
    T data; 
    LRUCacheEntry* prev; 
    LRUCacheEntry* next; 
}; 

template<class K, class T> 
class LRUCache 
{ 
private: 
    hash_map< K, LRUCacheEntry<K,T>* > _mapping; 
    vector< LRUCacheEntry<K,T>* >  _freeEntries; 
    LRUCacheEntry<K,T> *   head; 
    LRUCacheEntry<K,T> *   tail; 
    LRUCacheEntry<K,T> *   entries; 
public: 
    LRUCache(size_t size){ 
     entries = new LRUCacheEntry<K,T>[size]; 
     for (int i=0; i<size; i++) 
      _freeEntries.push_back(entries+i); 
     head = new LRUCacheEntry<K,T>; 
     tail = new LRUCacheEntry<K,T>; 
     head->prev = NULL; 
     head->next = tail; 
     tail->next = NULL; 
     tail->prev = head; 
    } 
    ~LRUCache() 
    { 
     delete head; 
     delete tail; 
     delete [] entries; 
    } 
    void put(K key, T data) 
    { 
     LRUCacheEntry<K,T>* node = _mapping[key]; 
     if(node) 
     { 
      // refresh the link list 
      detach(node); 
      node->data = data; 
      attach(node); 
     } 
     else{ 
      if (_freeEntries.empty()) 
      { 
       node = tail->prev; 
       detach(node); 
       _mapping.erase(node->key); 
       node->data = data; 
       node->key = key; 
       attach(node); 
      } 
      else{ 
       node = _freeEntries.back(); 
       _freeEntries.pop_back(); 
       node->key = key; 
       node->data = data; 
       _mapping[key] = node; 
       attach(node); 
      } 
     } 
    } 

    T get(K key) 
    { 
     LRUCacheEntry<K,T>* node = _mapping[key]; 
     if(node) 
     { 
      detach(node); 
      attach(node); 
      return node->data; 
     } 
     else return NULL; 
    } 

private: 
    void detach(LRUCacheEntry<K,T>* node) 
    { 
     node->prev->next = node->next; 
     node->next->prev = node->prev; 
    } 
    void attach(LRUCacheEntry<K,T>* node) 
    { 
     node->next = head->next; 
     node->prev = head; 
     head->next = node; 
     node->next->prev = node; 
    } 
}; 

編譯resualt：

In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/backward/hash_map:60, 
       from Source.C:3: 
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/backward/backward_warning.h:28:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. 
Source.C:6: error: âstdextâ is not a namespace-name 
Source.C:6: error: expected namespace-name before â;â token 
Source.C:21: error: ISO C++ forbids declaration of âhash_mapâ with no type 
Source.C:21: error: expected â;â before â<â token 
Source.C: In member function âvoid LRUCache<K, T>::put(K, T)â: 
Source.C:46: error: â_mappingâ was not declared in this scope 
Source.C: In member function âT LRUCache<K, T>::get(K)â: 
Source.C:77: error: â_mappingâ was not declared in this scope 

有人可以告訴我，我怎麼能解決「stdext」的問題？ 我想它會解決其餘的錯誤。 TNX！

Answer 1

stdext是一個MSVC擴展，但是你正在用GCC編譯linux，所以它不可用。 GCC具有類似的擴展名，但其標頭爲ext/hash_map，位於__gnu_cxx名稱空間中，而不是stdext。 MSVC和GCC的hash_maps都有類似的界面，但是如果我記得正確的話，就會有細微的差別。

如果可以，請使用C++ 11的unordered_map。如果不這樣做，也許你有TR1可用，並且std::tr1::unordered_map。作爲最後的回退，考慮Boost的無序容器（作爲TR1和C++ 11接口的基礎）。

編輯 我剛剛注意到您正在使用GCC 4.4.x，TR1在那裏可用。唯一的問題是，如果你使用MSVC在windows上編譯相同的代碼，那麼我不相信TR1在那裏可用（我有VC8和VC9可用，而且它不可用，我相信他們直接去了開始在VC10中支持C++ 11庫，完全跳過TR1）。