FIFO Map in c++

Question

I need to store a number of key/value pairs and access them again referenced by key - not necessarily in a map, although this seems natural. Additionally, if the map exceeds a certain size, I need to delete the oldest pairs.

Is there a way to implement this using a map or a similar structure somehow combining a map and a queue in C++11?

UPDATE: I wanted to this with a std::unsorted_map. Unfortunately I'm heavily missing std::map functions which would help. The unordered list seems neither to support rbegin() nor does its iterator support the --operator, so that I can't use end() either.

Is there a better way than iterating through a loop to size()-1?

Answer 1

There's no unique solution for this problem, the simplest one would be to use an auxiliary queue for storing the keys in order of insertion.

map<string, string> m_myMap;
queue<string>       m_myQueue;

void insert(const string& key, const string& value) {
  m_myMap.insert(make_pair(key, value));
  m_myQueue.push(key);
}

void deleteOldOnes() {
  while (m_myQueue.size() > MAX_SIZE) {
   m_myMap.erase(m_myQueue.front());
   m_myQueue.pop();
  }
}

You keep using the map for accessing the elements by key, the queue should not be used anywhere else than in the two methods above.

Answer 2

I had the same problem every once in a while and here is my solution: https://github.com/nlohmann/fifo_map. It's a header-only C++11 solution and can be used as drop-in replacement for a std::map.

Example

#include "src/fifo_map.hpp"

// for convenience
using nlohmann::fifo_map;

int main() {
    // create fifo_map with template arguments
    fifo_map<int, std::string> m;

    // add elements
    m[2] = "two";
    m[3] = "three";
    m[1] = "one";

    // output the map; will print
    // 2: two
    // 3: three
    // 1: one
    for (auto x : m) {
        std::cout << x.first << ": " << x.second << "\n";
    }

    // delete an element
    m.erase(2);

    // re-add element
    m[2] = "zwei";

    // output the map; will print
    // 3: three
    // 1: one
    // 2: zwei
    for (auto x : m) {
        std::cout << x.first << ": " << x.second << "\n";
    }
}

Note how the fifo_map's elements are always printed in the order of the insertion. Deletion of old elements is not implemented, but this extension should not be too difficult.