Fixed capacity unordered_map

Question

I have a need for a container that behaves like an unordered_map, but has a fixed capacity, and an eviction policy where the least recently inserted key-value pair is chosen to be evicted when an insertion is performed at capacity.

I've implemented this by creating a container which combines a regular unordered_map with a queue of iterators (implemented as a circular array). When a new item is inserted the iterator at the end of the queue is erased.

fixed_size_unordered_map

#include <array>
#include <unordered_map>

template<typename Key, typename U, std::size_t capacity>
class fixed_size_unordered_map {
    using iterator = typename std::unordered_map<Key, U>::iterator;
    using size_type = typename std::unordered_map<Key, U>::size_type;
    using value_type = typename std::unordered_map<Key, U>::value_type;

public:
    fixed_size_unordered_map() { iter_queue.fill(items.end()); }
    fixed_size_unordered_map(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map& operator=(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map(fixed_size_unordered_map&&) = default;
    fixed_size_unordered_map& operator=(fixed_size_unordered_map&&) = default;

    size_type count(const Key& key) const {
        return items.count(key);
    }

    const Key& at(const Key& key) const {
        return items.at(key);
    }

    std::pair<iterator, bool> insert(const value_type &v) {
        if(iter_queue[queue_idx] != items.end()){
            items.erase(iter_queue[queue_idx]);
        }
        const auto ret = items.insert(v);
        if(ret.second){
            iter_queue[queue_idx] = ret.first;
            queue_idx = (queue_idx + 1) % capacity;
        }
        return ret;
    }

    /* could implement more map<T, U> delegates as appropriate, the above are the ones
     * I actually need for my use case */

protected:
    std::unordered_map<Key, U> items;

    std::array<iterator, capacity> iter_queue;
    std::size_t queue_idx{0};
};

Example usage:

fixed_size_unordered_map<int, int, 10> m;
for(int i=0; i<=10; ++i){
    m.insert(std::make_pair(i, 2*i*i));
}
std::cout << m.at(10) << "\t" << m.at(1) << "\t" << m.count(0) << std::endl;

Answer 1

template<typename Key, typename U, std::size_t capacity>
class fixed_size_unordered_map {

The underlying map allows for policy customizations of the allocator, key comparator, and hash. You may want to provide these customization points to users.

---

    using iterator = typename std::unordered_map<Key, U>::iterator;
    using size_type = typename std::unordered_map<Key, U>::size_type;
    using value_type = typename std::unordered_map<Key, U>::value_type;

Are these common type definitions intended to be private?

---

    fixed_size_unordered_map(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map& operator=(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map(fixed_size_unordered_map&&) = default;
    fixed_size_unordered_map& operator=(fixed_size_unordered_map&&) = default;

If you explicitly define any of the special member functions for a class, you must define them all. The following five are considered special member functions. (see Rule of Zero/Three/Five)

• Destructor
• Copy Constructor
• Copy Assignment
• Move Constructor
• Move Assignment

Either explicitly provide the missing destructor (Rule of Five) or don't explicitly define any of them (Rule of Zero).

---

    if(iter_queue[queue_idx] != items.end()){
        items.erase(iter_queue[queue_idx]);
    }
    const auto ret = items.insert(v);
    if(ret.second){

Undefined behavior here. If the iter_queue is full, you erase no matter what happens. If insert succeeds, an iterator overwrites the current invalid iterator in the LRU. If insertion doesn't succeed, nothing happens to the LRU and the current iterator is just invalid.

Check before erasing. Erase when inserting. Determine how you want the LRU to behave on failure to insert.

---

Consider using a circular buffer or writing your own LRU cache adaptor for some buffer type. By decoupling the LRU functionality, this object can focus on just adapting its interface to the composed-from objects. It also removes the need to explicitly define a default constructor (unless you define a conversion ctor).