2
\$\begingroup\$

Here is a class that stores a single value into the limited cache. If cache is full, it will remove the oldest element to make a space for a new value. I'm using 2 structures to accomplish this because I need a fast lookup. I'm not very confident this is the best approach. Cache will contain a small amount of data (lets say 1000 elements).

#include <unordered_set>
#include <queue>

template <class T>
class Cache{

private:
    int _maxSize;
    std::unordered_set<T> _set;
    std::queue<T> _queue;

public:
    explicit Cache(int maxSize) : _maxSize(maxSize){}

    bool add(T value){
        if(_set.find(value) == _set.end()){ // // if not exists in set
            if(_set.size() == _maxSize){ // if set is 'full'
                _set.erase(_queue.front()); // delete the oldest value from the set
                _queue.pop(); // delete oldest value from queue
            }
            _queue.push(value); // push new value into queue
            _set.insert(value);  // insert new value into set
            return true;
        }
        return false;
    }

    int size(){
        return static_cast<int>(_set.size());
    }
};
\$\endgroup\$
3
\$\begingroup\$
  • Naming of data members: I would avoid duplicating the information that carries with the type. Can you think of something more meaningful?

  • Unsigned vs. signed integer for handling the size: as the maximum size is passed to the contructor as an int, static_cast<int>(_set.size()) should be safe. However, when it's foreseeable that you'll implement the class template using containers from the standard library (they all use std::size_t for their sizes), why not go with std::size_t for Cache, too?

  • Related to the above: always compile with warnings enabled. clang++ -Wall -pedantic -Wsign-conversion -Wextra -std=c++11 gives me

    warning: comparison of integers of different signs [...]

    if(_set.size() == _maxSize){ // if set is 'full'
    

    Again, as _maxSize is an int, this can be considered a non-issue in practice, but it's still somewhat brittle, if you change some implementation details later on.

  • You can only instantiate the Cache template when T mets the standard hash container requirements (i.e., a std::hash specialization is available as well as a comparison operator). To make your class template more reusable, consider adding template parameters that can be passed to std::unordered_set. If they have sensible defaults, you don't need to specify them most of the time.

    template <class T, class Hash = std::hash<T>, class EqualTo = std::equal_to<T>>
    class Cache {
        std::unordered_set<T, Hash, EqualTo> _set;
        // ...
    };
    
  • When caching an object, you save it twice, one in _queue and once in _set. For small objects, the duplication might be acceptable, but what if T is large? Remember that std::unordered_map doesn't invalidate iterators/pointers upon insertion and removal of entries. Consider a std::queue of iterators into _set.

  • Passing T by value in bool add(T value) can be a reasonable choice as long as you std::move it when it's used the last time and T supports move semantics. In your case:

    bool add(T value) {
       // ...
       _queue.push(value); // Don't move here
       _set.insert(std::move(value));  // ... but here!
    }
    

    You could also consider an overload set bool add(const T&) and bool add(T&&) instead as std::vector::push_back does for example.

  • When you worry about performance and you have varying max. cache sizes known at compile time, consider adding a non-type std::size_t template parameter to Cache. This way, you could specialize on smaller caches to e.g. use std::vector instead of std::unordered_map, which can be faster due fewer cache (ha!) misses. You need to do some benchmarking first though, and take different sizeof(T) into account.

  • A last note on performance: std::unordered_set was designed as a drop-in replacement for std::set. That's why it doesn't invalidate iterators/pointers into an instance, but that's also why it's not the fastest hash set. Of course, make sure to benchmark this properly, but you might want to have a look at some open address hash set, e.g. the one provided by abseil could be an option.

\$\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.