Implement a LRU Cache in C++ - compilation error

Question

I need to Implement a LRU Cache in C++. I have this code and i have problems while compiling:

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

compile 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

can someone tell me how can i fix the "stdext" problem? I guess it will solve the rest errors. TNX!

Answer 1

stdext is an MSVC extension, but you're compiling on linux with GCC, so it's not available. GCC has a similar extension, but its header is ext/hash_map, and is in the __gnu_cxx namespace, rather than stdext. Both MSVC and GCC's hash_maps have similar interfaces, but if I recall correctly, there are subtle differences.

If you can, utilize C++11's unordered_map. Failing that, maybe you have TR1 available, and std::tr1::unordered_map. As a final fallback, consider Boost's unordered containers (that served as a basis for TR1 and C++11's interfaces).

Edit I just noticed you're using GCC 4.4.x, TR1 is available there. The only issue would be if you're compiling the same code on windows with MSVC, as well, I do not believe TR1 is available there (I have VC8 and VC9 available, and it's not available in either. I believe they went straight to start supporting C++11 libraries in VC10, skipping TR1 completely).