CODEWITHSUNDEEP
c++containersstd
Danvil
Danvil

Reputation: 22991

Unique membership FIFO container

I need a first-in first-out queue which holds IDs with the catch that an ID should only be added if it is not already in the queue.

The best way I can think of is this:

typedef unsigned ID;
struct UniqueFifo
{
private:
   std::set<ID> ids; // keep track of what is already in
   std::queue<ID> fifo; // keep in fifo order
public:
   void push(ID x) {
       // only add to queue if not already in it
       if(ids.find(x) == ids.end()) {
           fifo.push(x);
           ids.insert(x);
       }
   }
   ID pop() {
       // pop from queue
       ID x = fifo.front();
       fifo.pop();
       // and also remove from map
       ids.erase(x);
       return x;
   }
};

Is there are more elegant way of doing this with C++ STL containers?

Upvotes: 2

Views: 1165

Answers (3)

Mike Seymour
Mike Seymour

Reputation: 254451

Using a second data structure like that, optimised for insertion and searching, is the most scalable solution; but if the queue never gets particularly large, then it might be more efficient (and certainly simpler) to do a linear search in the queue itself. You'll need deque itself, rather then the queue adapter, in order to access the contents.

If it is large enough to justify a searchable "index", then consider using unordered_set if available, or some other hash-based set if not; that's likely to be faster, if you only require uniqueness and not any particular ordering.

Your code needs to insert the ID into the set as well as the queue. Conveniently, you can combine this with the check for uniqueness, so that only a single search is needed:

if (ids.insert(x).second) {
    fifo.push(x);
}

You might also consider storing set iterators, rather than values, in the queue, to make erasing more efficient.

Upvotes: 5

Johan
Johan

Reputation: 3778

It's not bad at all. I can see other way to do this, mostly using one container (because the only "problem" that I see is that you're using 2 containers and so have to assert all the time that they are consistent with each other), but they are not more elegant and maybe cost even more.

IMHO leep this design (at least this interface) using a std::unordered_set instead of a std::set until you can benchmark your performances. After that you may have no problem or maybe the extra lookup in std::set will be too high for you. In this case you may try to keep a std::queue<std::pair<ID, std::unordered_set<ID>::const_iterator>> to ease the erasure (benefits from the fact that std::set and std::unordered_set iterator are not invalidated by addition or removal if the removal is not on there element).

But do not do this unless you need greater performances. Your code is simple and readable.

Upvotes: 2

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

Your solution is not bad, but you need to use a std::set<ID>, not a std::map(a map is used to map keys to values while you only care about values here). Also consider using std::unordered_set if c++11 is available.

Upvotes: 3

Related Questions