how to know whether a queue has contained an element

Discussion in 'C++' started by sg71.cherub@gmail.com, Dec 17, 2007.

  1. Guest

    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!
     
    , Dec 17, 2007
    #1
    1. Advertising

  2. siddhu Guest

    On Dec 17, 11:23 am, "" <>
    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);
    }
     
    siddhu, Dec 17, 2007
    #2
    1. Advertising

  3. Joe Greer Guest

    "" <> wrote in news:5480f1d7-
    :

    > 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
     
    Joe Greer, Dec 17, 2007
    #3
  4. Guest

    On Dec 17, 5:55 pm, Joe Greer <> wrote:
    > "" <> wrote in news:5480f1d7-
    > :
    >
    >
    >
    >
    >
    > > 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.
     
    , Dec 17, 2007
    #4
  5. Pete Becker Guest

    On 2007-12-17 15:39:13 -0500, ""
    <> 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)
     
    Pete Becker, Dec 17, 2007
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    689
    Russell Warren
    Jun 27, 2006
  2. Kris
    Replies:
    0
    Views:
    490
  3. Andries

    I know, I know, I don't know

    Andries, Apr 23, 2004, in forum: Perl Misc
    Replies:
    3
    Views:
    240
    Gregory Toomey
    Apr 23, 2004
  4. PerlFAQ Server
    Replies:
    0
    Views:
    109
    PerlFAQ Server
    Feb 8, 2011
  5. PerlFAQ Server
    Replies:
    0
    Views:
    119
    PerlFAQ Server
    Feb 18, 2011
Loading...

Share This Page