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

[Andy]

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

 

[Anand Hariharan]

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

 

[David Harmon]

On Thu, 07 Jun 2007 22:16:51 -0700 in comp.lang.c++, Andy

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.

 

[James Kanze]

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