5
\$\begingroup\$

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;
\$\endgroup\$
3
\$\begingroup\$
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).

\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback. Agree with all the initial points. A little confused by your final paragraph: you suggest "using a circular buffer" - I believe I already am with the iter_queue/queue_idx? I'm also not sure that replacing these with a full LRU cache would be ideal since it would be a pessimism in space (I would need to add something like a linked list of size capacity) \$\endgroup\$ – cloakedlearning Sep 17 '16 at 14:16

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.