0

我需要在 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;
    }
};

编译结果：

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”问题吗？我想它会解决其余的错误。天呐！

4

1 回答 1

0

stdext是一个 MSVC 扩展，但是你在 linux 上用 GCC 编译，所以它不可用。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 在那里可用。唯一的问题是，如果你在 Windows 上使用 MSVC 编译相同的代码，我不相信 TR1 在那里可用（我有可用的 VC8 和 VC9，但两者都不可用。我相信他们直接去了开始在 VC10 中支持 C++11 库，完全跳过 TR1）。

于 2013-06-20T18:44:22.407 回答