std::list: remove from front without deleting or looping through whole list

Discussion in 'C++' started by Andy, Jun 8, 2007.

  1. Andy

    Andy Guest

    Hello,

    I have the following situation:

    Thread A is allocating a dataset, doing some low-level calculations
    and storing a pointer to the dataset in a std::list via push_back.
    Thread B should retrieve the pointer to the first dataset in the list,
    remove it from the list, and do some high level analysis.

    The problem now is, how do I efficiently retrieve the pointer?

    Calling front() and then pop_front() deletes the dataset, i.e. calls
    its destructor, so this is not good, since I don't want to copy the
    datasets before calling pop_front(), because they are very large...
    Calling front() and remove(mylist.front()) does the job, but loops
    through the whole list and is thus also not very efficient..

    Is there any efficient way to retrieve the first object from the list,
    and remove the object then from the list, without looping through the
    whole list or deleting the object?

    If anybody has a good answer to the problem, I would really appreciate
    to hear it.

    Thanks a lot,
    Andy
     
    Andy, Jun 8, 2007
    #1
    1. Advertising

  2. On Jun 8, 12:16 am, Andy <> wrote:
    >
    > Thread A is allocating a dataset, doing some low-level calculations
    > and storing a pointer to the dataset in a std::list via push_back.
    > Thread B should retrieve the pointer to the first dataset in the list,
    > remove it from the list, and do some high level analysis.


    >From what you describe, you should consider std::deque. For that

    matter, measure std::vector and make sure it is not suitable.

    >
    > The problem now is, how do I efficiently retrieve the pointer?
    >
    > Calling front() and then pop_front() deletes the dataset, i.e. calls
    > its destructor, so this is not good, since I don't want to copy the
    > datasets before calling pop_front(), because they are very large...
    > Calling front() and remove(mylist.front()) does the job, but loops
    > through the whole list and is thus also not very efficient..
    >


    Not sure what you mean by "looping through the whole list". For all
    you know, your implementation caches std::list::front().

    > Is there any efficient way to retrieve the first object from the list,
    > and remove the object then from the list, without looping through the
    > whole list or deleting the object?
    >


    By erasing the first element, you only lose the pointer that was
    stored in that element. You don't delete the object. I assume you
    have another pointer to the same object? If you don't, and you just
    erase the first element, you leak memory.

    - Anand
     
    Anand Hariharan, Jun 8, 2007
    #2
    1. Advertising

  3. Andy

    David Harmon Guest

    On Thu, 07 Jun 2007 22:16:51 -0700 in comp.lang.c++, Andy
    <> wrote,
    >Thread A is allocating a dataset, doing some low-level calculations
    >and storing a pointer to the dataset in a std::list via push_back.
    >Thread B should retrieve the pointer to the first dataset in the list,
    >remove it from the list, and do some high level analysis.
    >
    >The problem now is, how do I efficiently retrieve the pointer?
    >
    >Calling front() and then pop_front() deletes the dataset, i.e. calls
    >its destructor,


    No, it doesn't, according to what you have so far described.
    The list merely stores pointer values. It has no idea about whatever
    those pointers might point to and will never call destructors at all.
     
    David Harmon, Jun 8, 2007
    #3
  4. Andy

    James Kanze Guest

    On Jun 8, 7:16 am, Andy <> wrote:

    > I have the following situation:


    > Thread A is allocating a dataset, doing some low-level calculations
    > and storing a pointer to the dataset in a std::list via push_back.
    > Thread B should retrieve the pointer to the first dataset in the list,
    > remove it from the list, and do some high level analysis.


    > The problem now is, how do I efficiently retrieve the pointer?


    > Calling front() and then pop_front() deletes the dataset, i.e. calls
    > its destructor, so this is not good,


    If the list contains pointers, it doesn't. It just removes the
    pointer from the list. (It calls the destructor of the pointer,
    but the destructor for a pointer is a no-op.)

    > since I don't want to copy the
    > datasets before calling pop_front(), because they are very large...
    > Calling front() and remove(mylist.front()) does the job, but loops
    > through the whole list and is thus also not very efficient..


    > Is there any efficient way to retrieve the first object from the list,
    > and remove the object then from the list, without looping through the
    > whole list or deleting the object?


    > If anybody has a good answer to the problem, I would really appreciate
    > to hear it.


    I'm not sure I understand the problem. If you're list contains
    pointers, nothing gets deleted by pop_front. If it contains
    objects, you copy both on insertion and of removal. (For queues
    between threads, I usually use auto_ptr in the interface, so it
    is clear who owns what. And most of the time, I find deque more
    appropriate than list.)

    --
    James Kanze (Gabi Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jun 8, 2007
    #4
    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. \A_Michigan_User\
    Replies:
    2
    Views:
    939
    \A_Michigan_User\
    Aug 21, 2006
  2. dkmd_nielsen
    Replies:
    5
    Views:
    170
    dkmd_nielsen
    Mar 8, 2007
  3. Replies:
    0
    Views:
    134
  4. Aaron
    Replies:
    2
    Views:
    577
    dhtml
    Apr 10, 2011
  5. crea
    Replies:
    2
    Views:
    441
    Nobody
    Dec 28, 2012
Loading...

Share This Page