how to know whether a queue has contained an element

S

sg71.cherub

HI all,

I use <queue> of STL. Before pushing an element into the queue, how to
check whether the queue has contained the element? i.e. I want the
queue has no duplicated elements. Is ther Contains() function?

e.g.

#include <queue>

int main(void)
{
queue<int> q;
q.push(1);
q.push(2);

// q.push(1); // since q now contains "1", q should not push "1"
again.

// something like
// if (!q.Contains(1))
// {
// q.push(1);
// }

return 0;
}


many thanks indeed!
 
S

siddhu

HI all,

I use <queue> of STL. Before pushing an element into the queue, how to
check whether the queue has contained the element? i.e. I want the
queue has no duplicated elements. Is ther Contains() function?

e.g.

#include <queue>

int main(void)
{
queue<int> q;
q.push(1);
q.push(2);

// q.push(1); // since q now contains "1", q should not push "1"
again.

// something like
// if (!q.Contains(1))
// {
// q.push(1);
// }

return 0;

}

many thanks indeed!

you can use deque instead of queue if you want data structure to
behave as queue. Otherwise you can use set.

deque<int> q;
q.push_back(1);
q.push_back(2);

deque<int>::iterator it = find(q.begin(),q.end(),1);
if(it != q.end())
{
q.push_back(1);
}
 
J

Joe Greer

HI all,

I use <queue> of STL. Before pushing an element into the queue, how to
check whether the queue has contained the element? i.e. I want the
queue has no duplicated elements. Is ther Contains() function?

e.g.

#include <queue>

int main(void)
{
queue<int> q;
q.push(1);
q.push(2);

// q.push(1); // since q now contains "1", q should not push "1"
again.

// something like
// if (!q.Contains(1))
// {
// q.push(1);
// }

return 0;
}


many thanks indeed!

No. Queues (sadly imho) implement a fairly pure concept of a queue and
the only interfaces to it are via push() and pop(). I don't suppose
your dataset is such that looking and the front and back items can tell
you? That would be the easiest. :) However, the easiest solution
doesn't usually work. So...

The choices are to either use a different container which supports push
and pop functionality, but also searchability (like deque or list) or to
use a searchable container to track the 'key' values as they are pushed
and popped (sets fall pretty naturally into this category).

If you expect queue sizes to remain pretty small (say less than a 1000
items) then replacing your queue with a deque and using std::find() to
check the contents would probably be fine. Otherwise you could consider
using a container that is quick to search such as std:set,
unordered_set, or hash_set to track the contents of the queue. The
tracking container need only contain 'key' data, so if your object is
large or expensive to construct, you can reduce the data stored in the
tracking collection.

Again, not knowing your data, but you could also keep the data in the
set and push and pop the 'key' values. Your app would then pop the
'key' value, look up the data in the set, remove it and process it.

Anyway, those are some thoughts on how to approach the problem.

joe
 
S

sg71.cherub

(e-mail address removed):












No. Queues (sadly imho) implement a fairly pure concept of a queue and
the only interfaces to it are via push() and pop(). I don't suppose
your dataset is such that looking and the front and back items can tell
you? That would be the easiest. :) However, the easiest solution
doesn't usually work. So...

The choices are to either use a different container which supports push
and pop functionality, but also searchability (like deque or list) or to
use a searchable container to track the 'key' values as they are pushed
and popped (sets fall pretty naturally into this category).

If you expect queue sizes to remain pretty small (say less than a 1000
items) then replacing your queue with a deque and using std::find() to
check the contents would probably be fine. Otherwise you could consider
using a container that is quick to search such as std:set,
unordered_set, or hash_set to track the contents of the queue. The
tracking container need only contain 'key' data, so if your object is
large or expensive to construct, you can reduce the data stored in the
tracking collection.

Again, not knowing your data, but you could also keep the data in the
set and push and pop the 'key' values. Your app would then pop the
'key' value, look up the data in the set, remove it and process it.

Anyway, those are some thoughts on how to approach the problem.

joe- Hide quoted text -

- Show quoted text -

Thank you both siddhu and Joe for correct and swift comments on
queue.

I believe queue is very suitable when implementing FIFO (providing
only pop() and push() interfaces), so it is the case for my project.
However, it is indeed lack of "searchablity". I have switched to
deque, working a little bit carefully with pop_front() and push_back()
to achieve the same FIFO.

Many thanks indeed.
 
P

Pete Becker

I believe queue is very suitable when implementing FIFO (providing
only pop() and push() interfaces), so it is the case for my project.
However, it is indeed lack of "searchablity". I have switched to
deque, working a little bit carefully with pop_front() and push_back()
to achieve the same FIFO.

That's not quite the right answer, though, since, as you say, you have
to work carefully with a deque. Use a deque, because it does the things
you need, but wrap it in a class that exposes only the operations you
need. Use std::queue as an example of this approach.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,836
Latest member
BuyBlissBitesCBD

Latest Threads

Top