what is the usefule way to run over a queue in c++

Question

As much as I read about Queue interface I can only access the elements in the back and the front of the queue.

my question:

I want to check if "the same element" exist in the queue before I add a new one.

My first solution was to use for loop, run SIZE_OF_QUEUE iterations and every time to check if the element exist in the front of the queue and "raise a flag" if it does. In any case the element is poped and push to the back of the queue, and in any case the same number of iteration will be executed.

The disadvantage is that even if the element was found right away, the for loop will keep running.

I want to use a queue for this purpose, for I have to pop the oldest element first when I use them.

Is there another way to do it more efficiently?

thanks

`I must use a queue for this purpose.` going by what you have written I'm not sure that you should. — user657267, Jan 15 '15 at 23:58
There is no magical way to inspect the elements of the `std::queue`. Ideally check the elements when they are added or use a different container (I know you say you can't). — Galik, Jan 16 '15 at 00:09
@Galik: Actually, [there is](http://stackoverflow.com/questions/3033483/how-can-i-construct-or-return-the-underlying-deque-from-a-stack/3034221#3034221). But you don't want to do that. — Mike Seymour, Jan 16 '15 at 01:08

score 3 · Accepted Answer · answered Jan 16 '15 at 00:01

A deque can do what you require as it allows random access of elements. It can do everything a queue can do with the addition of popping from the back as well as iterating through all the elements.

If you really must use a queue, you can use a dummy object or keep a reference of the first item in the list and stop when you reach it again but both those solutions are fairly hacky. Judging by your desired use case, a queue isn't what you need.

Axalo · Answer 2 · 2015-01-16T02:24:57.783

0

EDIT:

since accessing elements in a deque by offsetting a pointer to another element causes undefined behavior you can use this instead:

template<typename T>
struct iterable_queue : public std::queue<T>
{
    typedef container_type Cont;

    typename Cont::iterator begin()
    {
        return c.begin();
    }

    typename Cont::const_iterator begin() const
    {
        return c.begin();
    }

    typename Cont::iterator end()
    {
        return c.end();
    }

    typename Cont::const_iterator end() const
    {
        return c.end();
    }
};

edited Jan 16 '15 at 02:24

answered Jan 16 '15 at 00:25

Axalo

2,953
4
25
39

In the likely event the Op is using the standard `std::queue` adapter class, it defaults to using a `std:deque` as the underlying sequence container. this logic will fail horribly if there is more than one page in said-deque. In short, *don't do this*. – WhozCraig Jan 16 '15 at 00:28
`std::queue` is not guaranteed to store all objects in contiguous memory, it could be using an `std::list`, so the shown code is UB. – nwp Jan 16 '15 at 00:29
If you really want to do it this way, then you can access the container via the protected member `queue::c`, without the undefined behaviour of these hideous casts. But don't do that either. Just use a more appropriate container in the first place. – Mike Seymour Jan 16 '15 at 01:18
In this edited version you cast the queue into its underlying type. If the underlying type is not the first member of the queue this does not work. UB yet again. – nwp Jan 16 '15 at 01:21
The std::queue may have an int as the first element. Your code casts that int into a container and tries to access it. – nwp Jan 16 '15 at 01:58
As seen [here](http://en.cppreference.com/w/cpp/container/queue), you can access the underlying container (which is named `c`) directly when inheriting from `std::queue`. – Chnossos Jan 16 '15 at 02:16
@nwp i wasn't casting the first element, i was casting the this pointer. Nevertheless I changed it so that iterable_queue accesses the underlying container directly without casting as Chnossos suggested. – Axalo Jan 16 '15 at 02:31

score 0 · Answer 3 · answered Jan 16 '15 at 00:29

right now every time you insert to the queue, you iterate all the elements, which is pretty time consuming. The time complexity of Enqueue() goes up from O(1) to O(n).

if you could sacrifice some memory(based on the scale of your data), you could maintain a hash table with your queue. Every time you insert something, first check whether that is in the hashtable. If so, insert to both hashtable and queue. When you do Dequeue(), remove the element in hashtable as well. In this way, your time complexity for Enqueue and Dequeue are still O(1). but as I said, you use additional memory for the gain.

what is the usefule way to run over a queue in c++

3 Answers3