Cache with limited size; If full remove the oldest 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 &lt;unordered_set&gt;
#include &lt;queue&gt;

template &lt;class T&gt;
class Cache{

private:
    int _maxSize;
    std::unordered_set&lt;T&gt; _set;
    std::queue&lt;T&gt; _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&lt;int&gt;(_set.size());
    }
};
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&lt;int&gt;(_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 &lt;class T, class Hash = std::hash&lt;T&gt;, class EqualTo = std::equal_to&lt;T&gt;&gt;
class Cache {
    std::unordered_set&lt;T, Hash, EqualTo&gt; _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&amp;) and bool add(T&amp;&amp;) 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.