Need help regarding std::list

[William Payne]

Ok, in my program I have a std::list<Document*>, where Document is one of my
own classes.

I need to go through this list and check each item if it's ready for
deletion. If it's not, skip to next, if it's ready I take steps to delete
it. The thing is that the list is part of a gui application and the system
removes the Document* from the list during the execution of the loop body.
That means I cant use iterators to iterate over the list. So I tried using
the size of the list, like this:

while(m_documents.size())
{
Document* ptr = m_documents.front();

if(ptr->ready_for_deletion())
{
ptr->clean_up(); // This removes ptr from the list before next
iteration
}
}

The problem with that solution is that I get an endless loop for Documents
not ready for deletion. I need to determine if I've asked a document if it's
ready for deletion or not and loop until all documents have been deleted or
there are only non-ready documents left in the list. I can't think of a
solution. I could create a new list of only Documents ready for deletion and
then delete those, but that's not really an option because when I find a
document ready for deletion, I need to delete it right now, not a bit later.

Not sure I'm making much sense and maybe I'm off-topic. If so, I apologise.

/ WP

 

[Victor Bazarov]

Ok, in my program I have a std::list<Document*>, where Document is one of my
own classes.

I need to go through this list and check each item if it's ready for
deletion. If it's not, skip to next, if it's ready I take steps to delete
it. The thing is that the list is part of a gui application and the system
removes the Document* from the list during the execution of the loop body.
That means I cant use iterators to iterate over the list.

Yes, you can.

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it
{
Document *pd = *it;
if (pd->ready_for_deletion())
{
pd->clean_up();
delete pd;
it = doclist.erase(it);
}
else
++it;
}

RTFM.

[...]

Victor

 

[William Payne]

Ok, in my program I have a std::list<Document*>, where Document is one of
my own classes.

I need to go through this list and check each item if it's ready for
deletion. If it's not, skip to next, if it's ready I take steps to delete
it. The thing is that the list is part of a gui application and the
system removes the Document* from the list during the execution of the
loop body. That means I cant use iterators to iterate over the list.

Yes, you can.

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it
{
Document *pd = *it;
if (pd->ready_for_deletion())
{
pd->clean_up();
delete pd;
it = doclist.erase(it);
}
else
++it;
}

RTFM.

[...]

Victor

Thanks for quick reply, Victor. Interesting solution. Unfortunately, the
actual delete ptr_document; is called somewhere else (working under the
constrains of gui library), but I will see what I can do with your solution.

/ WP

 

[Victor Bazarov]

Ok, in my program I have a std::list<Document*>, where Document is one of
my own classes.

I need to go through this list and check each item if it's ready for
deletion. If it's not, skip to next, if it's ready I take steps to delete
it. The thing is that the list is part of a gui application and the
system removes the Document* from the list during the execution of the
loop body. That means I cant use iterators to iterate over the list.

Yes, you can.

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it
{
Document *pd = *it;
if (pd->ready_for_deletion())
{
pd->clean_up();
delete pd;
it = doclist.erase(it);
}
else
++it;
}

RTFM.

[...]

Victor

Thanks for quick reply, Victor. Interesting solution. Unfortunately, the
actual delete ptr_document; is called somewhere else (working under the
constrains of gui library), but I will see what I can do with your solution.

You can always extract the elements of the list to be deleted into
a separate list and then pass it somewhere else to be disposed of.

Victor

 

[William Payne]

William Payne wrote:

Ok, in my program I have a std::list<Document*>, where Document is one
of my own classes.

I need to go through this list and check each item if it's ready for
deletion. If it's not, skip to next, if it's ready I take steps to
delete it. The thing is that the list is part of a gui application and
the system removes the Document* from the list during the execution of
the loop body. That means I cant use iterators to iterate over the list.

Yes, you can.

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it
{
Document *pd = *it;
if (pd->ready_for_deletion())
{
pd->clean_up();
delete pd;
it = doclist.erase(it);
}
else
++it;
}

RTFM.


[...]

Victor

Thanks for quick reply, Victor. Interesting solution. Unfortunately, the
actual delete ptr_document; is called somewhere else (working under the
constrains of gui library), but I will see what I can do with your
solution.

You can always extract the elements of the list to be deleted into
a separate list and then pass it somewhere else to be disposed of.

Victor

Well, say I have this loop (modified yours):
for(list<Document*>::iterator itr = m_documents.begin();
itr != m_documents.end();
) // Note: No ++itr;
{
Document* doc = *itr;

++itr;

if(doc->ready_for_deletion())
{
doc->clean_up(); /* triggers a removal of doc from list elsewhere
*/
}
}

Is itr still valid if doc->clean_up() triggers the system to remove doc from
the list before the next iteration begins?

Right now I wish I could do delete this; in the document class, heh.

/ WP

 

[Nicolas Pavlidis]

Victor Bazarov wrote:

[snipp]

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it

for(std::list<Document*>::iterator it = doclist.begin(),
std::list<Docuemnt*>::iterator end_mark = doclist.end();
it != end_mark)

Only for performance reason

SCNR && best regards
Nicolas

 

[Victor Bazarov]

William Payne wrote:


Ok, in my program I have a std::list<Document*>, where Document is one
of my own classes.

I need to go through this list and check each item if it's ready for
deletion. If it's not, skip to next, if it's ready I take steps to
delete it. The thing is that the list is part of a gui application and
the system removes the Document* from the list during the execution of
the loop body. That means I cant use iterators to iterate over the list.

Yes, you can.

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it
{
Document *pd = *it;
if (pd->ready_for_deletion())
{
pd->clean_up();
delete pd;
it = doclist.erase(it);
}
else
++it;
}

RTFM.



[...]

Victor


Thanks for quick reply, Victor. Interesting solution. Unfortunately, the
actual delete ptr_document; is called somewhere else (working under the
constrains of gui library), but I will see what I can do with your
solution.

You can always extract the elements of the list to be deleted into
a separate list and then pass it somewhere else to be disposed of.

Victor

Well, say I have this loop (modified yours):
for(list<Document*>::iterator itr = m_documents.begin();
itr != m_documents.end();
) // Note: No ++itr;
{
Document* doc = *itr;

++itr;

You can combine them:

Document* doc = *itr++;

but that's not the point.

if(doc->ready_for_deletion())
{
doc->clean_up(); /* triggers a removal of doc from list elsewhere
*/

This is not right IMO. Removal of the document pointer from the list
should be done by him who owns the list. Since you use 'm_documents'
as the variable name, it seems that (*this) object owns the list of
documents and should be deleting the elements from the list. That is
why I suggested 'erase' here.

}
}

Is itr still valid if doc->clean_up() triggers the system to remove doc from
the list before the next iteration begins?

I still think that

for (...

{
Document* pdoc = *itr;
if (pdoc->ready_for_deletion())
{
Do_whatever_cleanup_needed_elsewhere(); // pd is still
// in the list

// now extract the document from the list
itr = m_documents.erase();

Do_whatever_needed_to_dispose_of_(pdoc); // pd is not in
// the list anymore
}
else
++itr; // move to the next one
}

is _cleaner_ and easier to understand. Besides, there is a potential
bad situation. Imagine that you're working on the last element of the
list. When you do

Document *pdoc = *itr++;

'itr' now has the value of 'm_documents.end()', right? Now, let's
suppose that the last document is ready to be removed. The call to

doc->clean_up();

"triggers a removal". Suddenly, the list is shorter by one and its
end() is not where it was when you just did *itr++. You want to compare
the value of 'itr' to m_documents.end(), but it's not the same any more.
You get undefined behaviour because 'itr' doesn't necessarily have the
same value that 'end()' returns. That's why you _really_ need to erase
the element from the list _right_here_, in the same loop (or at least
get the "current end of the list" from your 'clean_up' function). What
is worse is if your 'clean_up' is in a different thread and it _really_
just "triggers" the removal, but doesn't complete it by the time it
returns the control to the caller (to your loop). That's why I also
suggested a simple extraction into a separate list and then removal of
those document in a different function or after this loop or wherever.

Right now I wish I could do delete this; in the document class, heh.

You can only do that if you are sure that no instances of Document are
created in any other way but by 'new'. It's not difficult to do, just
define a factory method in 'Document' class and always call it when you
need to instantiate a Document.

Victor

 

[Victor Bazarov]

Victor Bazarov wrote:

[snipp]

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it

for(std::list<Document*>::iterator it = doclist.begin(),
std::list<Docuemnt*>::iterator end_mark = doclist.end();
it != end_mark)

Only for performance reason

That assumes that the list doesn't change length during the loop
execution, which is _specifically_ *not* the case in the original
post. Please pay attention.

V

 

[William Payne]

William Payne wrote:



William Payne wrote:


Ok, in my program I have a std::list<Document*>, where Document is one
of my own classes.

I need to go through this list and check each item if it's ready for
deletion. If it's not, skip to next, if it's ready I take steps to
delete it. The thing is that the list is part of a gui application and
the system removes the Document* from the list during the execution of
the loop body. That means I cant use iterators to iterate over the
list.

Yes, you can.

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it
{
Document *pd = *it;
if (pd->ready_for_deletion())
{
pd->clean_up();
delete pd;
it = doclist.erase(it);
}
else
++it;
}

RTFM.



[...]

Victor


Thanks for quick reply, Victor. Interesting solution. Unfortunately, the
actual delete ptr_document; is called somewhere else (working under the
constrains of gui library), but I will see what I can do with your
solution.

You can always extract the elements of the list to be deleted into
a separate list and then pass it somewhere else to be disposed of.

Victor

Well, say I have this loop (modified yours):
for(list<Document*>::iterator itr = m_documents.begin();
itr != m_documents.end();
) // Note: No ++itr;
{
Document* doc = *itr;

++itr;

You can combine them:

Document* doc = *itr++;

but that's not the point.

if(doc->ready_for_deletion())
{
doc->clean_up(); /* triggers a removal of doc from list
elsewhere */

This is not right IMO. Removal of the document pointer from the list
should be done by him who owns the list. Since you use 'm_documents'
as the variable name, it seems that (*this) object owns the list of
documents and should be deleting the elements from the list. That is
why I suggested 'erase' here.

}
}

Is itr still valid if doc->clean_up() triggers the system to remove doc
from the list before the next iteration begins?

I still think that

for (...

{
Document* pdoc = *itr;
if (pdoc->ready_for_deletion())
{
Do_whatever_cleanup_needed_elsewhere(); // pd is still
// in the list

// now extract the document from the list
itr = m_documents.erase();

Do_whatever_needed_to_dispose_of_(pdoc); // pd is not in
// the list anymore
}
else
++itr; // move to the next one
}

is _cleaner_ and easier to understand. Besides, there is a potential
bad situation. Imagine that you're working on the last element of the
list. When you do

Document *pdoc = *itr++;

'itr' now has the value of 'm_documents.end()', right? Now, let's
suppose that the last document is ready to be removed. The call to

doc->clean_up();

"triggers a removal". Suddenly, the list is shorter by one and its
end() is not where it was when you just did *itr++. You want to compare
the value of 'itr' to m_documents.end(), but it's not the same any more.
You get undefined behaviour because 'itr' doesn't necessarily have the
same value that 'end()' returns. That's why you _really_ need to erase
the element from the list _right_here_, in the same loop (or at least
get the "current end of the list" from your 'clean_up' function). What
is worse is if your 'clean_up' is in a different thread and it _really_
just "triggers" the removal, but doesn't complete it by the time it
returns the control to the caller (to your loop). That's why I also
suggested a simple extraction into a separate list and then removal of
those document in a different function or after this loop or wherever.

Right now I wish I could do delete this; in the document class, heh.

You can only do that if you are sure that no instances of Document are
created in any other way but by 'new'. It's not difficult to do, just
define a factory method in 'Document' class and always call it when you
need to instantiate a Document.

Victor

Thanks for your reply, Victor. I guess I need to develop a new strategy to
solve this problem. The class that owns the list contains a callback
function that is called by the system, which complicates the matter.

/ WP

 

[David Hilsee]

Victor Bazarov wrote:

[snipp]

for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it

for(std::list<Document*>::iterator it = doclist.begin(),
std::list<Docuemnt*>::iterator end_mark = doclist.end();
it != end_mark)

Only for performance reason

That assumes that the list doesn't change length during the loop
execution, which is _specifically_ *not* the case in the original
post. Please pay attention.

Doesn't the iterator returned by std::list::end() remain valid even if
elements are removed or added from the list (say, via calls to erase() or
insert())? The list's iterators aren't supposed to be invalidated unless
the element to which the iterator is pointing has been removed. Is end() a
special case?

 

[Victor Bazarov]

Victor Bazarov wrote:

[snipp]


for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it

for(std::list<Document*>::iterator it = doclist.begin(),
std::list<Docuemnt*>::iterator end_mark = doclist.end();
it != end_mark)

Only for performance reason

That assumes that the list doesn't change length during the loop
execution, which is _specifically_ *not* the case in the original
post. Please pay attention.

Doesn't the iterator returned by std::list::end() remain valid even if
elements are removed or added from the list (say, via calls to erase() or
insert())? The list's iterators aren't supposed to be invalidated unless
the element to which the iterator is pointing has been removed. Is end() a
special case?

I don't know. I try always be on the safer side of things, so when I
am not sure, I'd rather not rely on some behaviour. For example, what
happens to 'end()' if you remove the last element?

V

 

[Tom Widmer]

Victor Bazarov wrote:

[snipp]


for (std::list<Document*>::iterator it = doclist.begin();
it != doclist.end();
) // note: no ++it

for(std::list<Document*>::iterator it = doclist.begin(),
std::list<Docuemnt*>::iterator end_mark = doclist.end();
it != end_mark)

Only for performance reason

That assumes that the list doesn't change length during the loop
execution, which is _specifically_ *not* the case in the original
post. Please pay attention.

Doesn't the iterator returned by std::list::end() remain valid even if
elements are removed or added from the list (say, via calls to erase() or
insert())? The list's iterators aren't supposed to be invalidated unless
the element to which the iterator is pointing has been removed. Is end() a
special case?

No. As you say, list::end() is never invalidated (unless the list
itself is destroyed).

Tom