Re: newbie Q.: GNU STL set<>, LinuxThreads, signals, setitimer => misbehavior

[Frantisek . Rysanek]

Dear Gentlemen,

thanks a lot for your responses.
Firstly, I should probably take a serious look at strong pointers,
maybe I'm indeed reinventing the wheel.

Regarding the problem of
i = end(); i++;
I would understand that you can't iterate past the end, operator++()
on end() should return end() again...


Secondly, I seem to have solved my problem in my clumsy ways,
and I guess the catch is elsewhere:

According to some other postings in the USENET groups,
on some STL containers, any modification (insertion, removal)
invalidates iterators - hence it's impossible to delete from such
containers while you iterate, even if you try to avoid trouble by
storing an iterator to the previous or next node.
According to that posting, this is a typical behavior with tree-based
containers such as map<> and set<>. According to my "research",
this is probably also true with the deque<>. I understand that any
deletion or addition in a balanced tree can cause its re-balancing.
Depending on how that's implemented, it may re-allocate nodes,
thus voiding any iterators. And, upon closer inspection, my
implementation of deque seems to store several elements
in one allocation unit, so that a deletion halfway through the
container may cause reshuffling of elements.

The only container known to me, that probably doesn't invalidate
iterators on deletion, ever, is the list<> - apparently a classic
doubly-linked circular list, with each node allocated separately.

As a hint, check the prototypes of the containers' erase() method.
If the erase() method returns a pointer to the next node after the one
just deleted, that container's erase() method doesn't invalidate
iterators. If the erase() method's return value is void,
don't bother to store the neighbor iterators "out of band",
they'll be invalidated anyway.

The one thing that puzzles me is that a banner comment in my
stl_tree.h (used to implement set<> and map<>) claims that
only the deleted iterator is invalidated, but no others.
That doesn't match my very fresh lesson learned from set<>.


In my application, I have several cases where I need to "delete
while iterating", but I also need associative access to the container
elements. In such cases, I use a helper vector<> to store my
"deletion candidates" (keys to the associative container) and
I delete them, based on that helper vector, only after I've finished
iterating across the basic set<> or map<>.

set<my_object*> my_set;

void process_timeouts()
{
 vector<my_object*> deletion_candidates;

   for (i = my_set.begin(); i != my_set.end(); i++)
   {
      if ((*i)->timed_out()
      {
         (*i)->bye_bye();
         deletion_candidates.push_back(*i);
      }
   }

   for (j = deletion_candidates.begin();
         j != deletion_candidates.end(); j++)
      my_set.erase(my_set.find(*j));
}

I have one or two cases where a plain list<> will do
- those are cases where I need to queue some operations,
I need to process their timeouts by iterating across the container,
but I don't need associative access to the elements.
In such cases, indeed I can "erase while iterating" e.g. using
the classic for(;;) loop, and I can even take advantage
of the erase() operation returning an iterator:

for (i = my_list.begin(); i != my_list.end(); /* i++ */)
{
   if (i->timed_out())
   {
      i->bye_bye();
      i = my_list.erase(i);
   }
   else  // this one's still okay, go on to the next one
      i++;
}


At this moment it seems that threads and signals have
nothing to do with my problem. I hope this is not proven
wrong when I apply more load :-)

Frank Rysanek