Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   how to know whether a queue has contained an element (http://www.velocityreviews.com/forums/t561767-how-to-know-whether-a-queue-has-contained-an-element.html)

sg71.cherub@gmail.com 12-17-2007 04:23 PM

how to know whether a queue has contained an element
 
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!

siddhu 12-17-2007 04:31 PM

Re: how to know whether a queue has contained an element
 
On Dec 17, 11:23 am, "sg71.che...@gmail.com" <sg71.che...@gmail.com>
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);
}

Joe Greer 12-17-2007 05:55 PM

Re: how to know whether a queue has contained an element
 
"sg71.cherub@gmail.com" <sg71.cherub@gmail.com> wrote in news:5480f1d7-
3e96-461e-9b06-765082a3ace0@s8g2000prg.googlegroups.com:

> 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

sg71.cherub@gmail.com 12-17-2007 08:39 PM

Re: how to know whether a queue has contained an element
 
On Dec 17, 5:55 pm, Joe Greer <jgr...@doubletake.com> wrote:
> "sg71.che...@gmail.com" <sg71.che...@gmail.com> wrote in news:5480f1d7-
> 3e96-461e-9b06-765082a3a...@s8g2000prg.googlegroups.com:
>
>
>
>
>
> > 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.

Pete Becker 12-17-2007 09:01 PM

Re: how to know whether a queue has contained an element
 
On 2007-12-17 15:39:13 -0500, "sg71.cherub@gmail.com"
<sg71.cherub@gmail.com> 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)



All times are GMT. The time now is 10:24 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.