2
\$\begingroup\$

I have tried to implement a Least Recently Used cache with only C++ STL containers. The main thing that I keep asking my self the static variable called garbage_val. Is it a good practice to have such a static variable just for garbage values?

template<typename Key, typename Value>
class LRU_Cache
{
struct Node
{
    Key k;
    Value v;
};

public:
static Value garbage_val;

LRU_Cache(unsigned int capacity)
{
    capacity_ = capacity;
}

Value get(Key key)
{
    auto node = cache_.find(key);

    if(node == cache_.end())
    {
        return garbage_val;
    }

    Value val = (*(node->second)).v;
    recentlyList_.erase(node->second);

    Node n; n.v = val; n.k = key;

    recentlyList_.push_back(n);
    cache_[key] = --recentlyList_.end();

    return val;
}

void set(Key key, Value val)
{
    auto node = cache_.find(key);

    if(node != cache_.end())
    {
        recentlyList_.erase(node->second);
    }
    else
    {
        evict_if_needed();
    }

    Node n; n.v = val; n.k = key;
    recentlyList_.push_back(n);
    cache_[key] = --recentlyList_.end();
}

void evict_if_needed()
{
    if(cache_.size() >= capacity_)
    {
        auto node = cache_.find(recentlyList_.begin()->k);
        recentlyList_.pop_front();
        cache_.erase(node);
    }
}

virtual ~LRU_Cache(void)
{
}

void print()
{
    std::cout << "Objects in Memory:" << std::endl;
    for(auto& c : cache_)
    {
        std::cout << "(" << c.first << "," << (*(c.second)).v << ")" << std::endl;
    }

    std::cout << "Recently used:" << std::endl;
    for(auto& r : recentlyList_)
    {
        std::cout << "(" << r.k << "," << r.v << ")" << std::endl;
    }
}
private:
LRU_Cache(void){}

std::unordered_map<Key, typename std::list<Node>::iterator> cache_;
std::list<Node> recentlyList_;
unsigned int capacity_;
};
template<typename Key,typename Value> Value LRU_Cache<Key,Value> ::garbage_val;
\$\endgroup\$
2
\$\begingroup\$

Is it a good practice to have such a static variable just for garbage values?

Maybe not:

  • garbage_val is a Value, so if you return it, then the caller doesn't know whether the get succeeded.
  • If garbage_val is supposed to be a magic number (an impossible Value), different users of the class might want different magic numbers ... so why isn't garbage_val an instance member instead of a static member?
  • Normally container classes expect the caller to check that iterator != end() before dereferencing the iterator.

Instead, the following methods might be appropriate:

// throws an exception if key does exist.
Value get(Key key) { ... }
// tests whether key exists: use this before calling get.
bool contains(Key key) { ... }
// return true and initializes value iff key exists.
// if key doesn't exist then valueOut is not initialized. 
bool tryGet(Key key, Value& valueOut) { ... }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.