5

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?

Marste
  • 627
  • 7
  • 22
  • [this may help](http://stackoverflow.com/questions/1262808/which-stl-container-should-i-use-for-a-fifo) and this from [C++ reference info](http://www.cplusplus.com/reference/queue/queue/) – Mike Jan 22 '14 at 17:34
  • Do you need to do lookups via the key, or is it just two pieces of data in a FIFO? – Marshall Clow Jan 22 '14 at 23:26
  • Yes, I really want to reference them by key. If there is no other way I would have to iterate through a queue, but there has to be some more elegant solution. – Marste Jan 23 '14 at 17:44

3 Answers3

6

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.

ichramm
  • 6,437
  • 19
  • 30
  • 1
    This is the general idea. However, this is invalid C++ code: you cannot have identifiers at file scope which start with an underscore. It’s easiest to avoid leading underscores everywhere. – Konrad Rudolph Jan 23 '14 at 17:58
  • 2
    Since those underscore identifiers are at the same scope as what looks to me like member functions (surely one wouldn't have `insert` and `deleteOldOnes` as well as the two container classes as freestanding globals?), I would presume that they're class scope, not file scope (for what it matters). – Damon Jan 23 '14 at 18:27
  • 2
    Dude, you got an upvote from me. I’m complaining about invalid code because the code you’ve posted is … invalid (and I’ve explained why; feel free to check the standard, section [global.names]). You don’t have to pass the code through the compiler to post it here. But you should post *valid* code. Of course. – Konrad Rudolph Jan 23 '14 at 18:27
3

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.

Niels Lohmann
  • 2,054
  • 1
  • 24
  • 49
1
#include<iostream>
#include<queue>
using namespace std;

main(){

    queue < pair <int,int> > Q; //First use a queue to store the pair wise values
    int a,b;
    // insert value to the queue as a pair
    for (int i=0;i<6;i++){ // i only insert 6 pairs
        cin>>a>>b;
        if (Q.size()>=3){   // if queue size is 3 than pop up the first value
            Q.pop();
        }

        Q.push(make_pair(a,b)); // insert a new pair into the queue
    }

    while(!Q.empty()){  // output the pairs on that queue
        cout<<Q.front().first<<" "<<Q.front().second<<endl;
        Q.pop();
    }

    return 0;
}
Imtiaz Emu
  • 479
  • 4
  • 5