Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > how to know whether a queue has contained an element

Reply
Thread Tools

how to know whether a queue has contained an element

 
 
sg71.cherub@gmail.com
Guest
Posts: n/a
 
      12-17-2007
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!
 
Reply With Quote
 
 
 
 
siddhu
Guest
Posts: n/a
 
      12-17-2007
On Dec 17, 11:23 am, "(E-Mail Removed)" <(E-Mail Removed)>
wrote:
> 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);
}
 
Reply With Quote
 
 
 
 
Joe Greer
Guest
Posts: n/a
 
      12-17-2007
"(E-Mail Removed)" <(E-Mail Removed)> wrote in news:5480f1d7-
http://www.velocityreviews.com/forums/(E-Mail Removed):

> 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
 
Reply With Quote
 
sg71.cherub@gmail.com
Guest
Posts: n/a
 
      12-17-2007
On Dec 17, 5:55 pm, Joe Greer <(E-Mail Removed)> wrote:
> "(E-Mail Removed)" <(E-Mail Removed)> wrote in news:5480f1d7-
> (E-Mail Removed):
>
>
>
>
>
> > 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- 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.
 
Reply With Quote
 
Pete Becker
Guest
Posts: n/a
 
      12-17-2007
On 2007-12-17 15:39:13 -0500, "(E-Mail Removed)"
<(E-Mail Removed)> said:

>
> 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.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
FAQ 4.42 How can I tell whether a certain element is contained in a list or array? PerlFAQ Server Perl Misc 0 02-18-2011 05:00 PM
FAQ 4.42 How can I tell whether a certain element is contained in a list or array? PerlFAQ Server Perl Misc 0 02-08-2011 11:00 PM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM



Advertisments