| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"" |
| Date: |
17 Dec 2007 10:23:52 AM |
| Object: |
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!
.
|
|
| User: "Joe Greer" |
|
| Title: Re: how to know whether a queue has contained an element |
17 Dec 2007 11:55:07 AM |
|
|
"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
.
|
|
|
| User: "" |
|
| Title: Re: how to know whether a queue has contained an element |
17 Dec 2007 02:39:13 PM |
|
|
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.
.
|
|
|
| User: "Pete Becker" |
|
| Title: Re: how to know whether a queue has contained an element |
17 Dec 2007 03:01:21 PM |
|
|
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)
.
|
|
|
|
|
|
| User: "siddhu" |
|
| Title: Re: how to know whether a queue has contained an element |
17 Dec 2007 10:31:54 AM |
|
|
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);
}
.
|
|
|
|
|
Related Articles |
|
|
