Мне нужно реализовать кэш LRU в C ++.
У меня есть этот код, и у меня есть проблемы при компиляции:
#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;
}
};
составить результат:
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!
stdext
является расширением MSVC, но вы компилируете на linux с GCC, поэтому оно недоступно. GCC имеет аналогичное расширение, но его заголовок ext/hash_map
и находится в __gnu_cxx
пространство имен, а не stdext
, И MSVC, и GCC hash_maps имеют схожие интерфейсы, но, если я правильно помню, есть тонкие различия.
Если можете, используйте unordered_map в C ++ 11. В противном случае, возможно, у вас есть TR1 и std::tr1::unordered_map
, В качестве последнего отступления рассмотрим неупорядоченные контейнеры Boost (которые послужили основой для интерфейсов TR1 и C ++ 11).
редактировать
Я только что заметил, что вы используете GCC 4.4.x, там доступен TR1. Единственная проблема будет, если вы компилируете тот же код в Windows с MSVC, я не верю, что TR1 доступен там (у меня есть VC8 и VC9, и он недоступен ни в одном из них. Я полагаю, что они пошли прямо к начать поддерживать библиотеки C ++ 11 в VC10, полностью пропуская TR1).
Других решений пока нет …