Mix between queue and set?

[daviddoria]

Is there a data structure that lets me push and pop things onto/off of a queue, but also doesn't allow duplicates?

E.g.
I want

queue a;
a.push(1);
a.push(2);
a.push(2);
a.push(3);

to only have 3 elements, because 2 was added twice so the second time it is just ignored.

Any ideas?

Thanks,
Dave

[mattjbond]

queue a;
a.push(1);
a.push(2);
a.push(2);
a.push(3);

to only have 3 elements, because 2 was added twice so the second time it is just ignored.

But you want this to have FIFO behaviour?

Why not create your own queue class, based on a deque for instance, which has a specialized push which will not allow duplicates. Simply peek at the last value pushed and if it is equal to the new one don't add then new one.

for exampe....

template<typename T>
class Queue
{
   std::deque<T> container;

public:
   ...

   void push( const T& elem ) 
   { 
      T last = c.back();
      if ( last == elem )
         return;
      c.push_back(elem); 
   }

   ... 
}

Something along those lines...
Obviously addign all the other functions you would require and providing error checking where appropriate.

[daviddoria]

mattjbond,

Thanks for the reply. That is a almost what I'm looking for, except it shouldn't only not allow duplicate elements adjacent to each other, duplicate elements should not be allowed at ANY position in the queue.

void push( const T& elem ) 
   { 
      
      if ( elem is already somewhere in the queue)
         return;
      c.push_back(elem); 
   }

This is the part that I didn't know how to do with a queue (without popping through the whole queue and then recreating it, which seems insanely inefficient).

Thanks,

Dave

[mattjbond]

Why can't you use one of the generic algorithms to search your container for duplicates?

find or find_if spring to mind. each of these will return an iterator to the found element if it exists or end if no matching elements are found.

If your find returns end then push your value.

void push( const T& elem ) 
   { 
      std::deque<T>::iterator pos = find( c.begin(), c.end(), elem );
      if ( pos == c.end())
         c.push_back(elem); 
   }

Something like that. Haven't tried that by the way, but it is where I think I would start...

[mattjbond]

Or if you want terser code just put the find in the if too.

void push( const T& elem ) 
   { 
      if ( find( c.begin(), c.end(), elem )== c.end())
         c.push_back(elem); 
   }

ps. don't forget to #include <algorithm>

[daviddoria]

Ah, great. I didn't see any functions to access elements of a queue other than the front and back, but I guess find from 'algorithm' can do exactly what I was looking for. Thanks a lot!

[Sky Diploma]

But you want this to have FIFO behaviour?

Why not create your own queue class, based on a deque for instance, which has a specialized push which will not allow duplicates. Simply peek at the last value pushed and if it is equal to the new one don't add then new one.

for exampe....

template<typename T>
class Queue
{
   std::deque<T> container;

public:
   ...

   void push( const T& elem ) 
   { 
      T last = c.back();
      if ( last == elem )
         return;
      c.push_back(elem); 
   }

   ... 
}

Something along those lines...
Obviously addign all the other functions you would require and providing error checking where appropriate.

This code doesnt remove duplicates if

queue a;
a.push(1);
a.push(2);
a.push(3);
a.push(2);

This was executed i assume!! I maybe wrong though.

[daviddoria]

Hmm am I doing something wrong? I am getting this error:

error: 'iterator' is not a member of 'std::queue<int, std::deque<int, std::allocator<int> > >'

Here is the code:

#include <iostream>
#include <queue>
#include <cstdlib>
#include <algorithm>

int main(int argc, char* argv[])
{
  std::queue <int> q;

  q.push(1);
  q.push(2);
  q.push(3);
  
  std::queue<int>::iterator pos = std::find( q.begin(), q.end(), 2);
  if ( pos == q.end())
    {
    std::cout << " not found" << endl;
    }
  else
    {
    std::cout << " not found" << endl;
    }
 
  return 0;
}

Thanks,

Dave

[daviddoria]

Ah, I guess I have to use a deque if I want an iterator.

[invisal]

Ah, I guess I have to use a deque if I want an iterator.

You can create your own class. using singly linked list to store data. Then make your class to behave like queue.

[mattjbond]

Ah, I guess I have to use a deque if I want an iterator.

Yes you should use a deque, which is just a double ended queue. The STL does provide a container adapter which will give queue behaviour. It does this in the same way your queue class does, by basing its functionality on deque and simply mapping its operations to the appropriate members of deque.