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

[James Dennett]

Frantisek.Rysanek@post.cz wrote:
> 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...

That's not how it works.  You can't iterate past the
end, so you MUST NOT try to do so.  If you do try to
do so, it's a bug in your program, and anything might
happen.

Common problems including crashing, getting an error
message (more common in "debug" builds), or, for many
implementations of std::list, finding yourself back
at begin().

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

The rules are more complex than that; they do end up
allowing traversal and removal together, but the rules
for each container need to be followed carefully.

> According to that posting, this is a typical behavior with tree-based
> containers such as map<> and set<>. 

Then that post is wrong; for node-based containers such
as those, inserting does not invalidate any iterators,
and removing items invalidates only iterators to those
items.

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

But that doesn't need to move any nodes, it just moves pointers.

> Depending on how that's implemented, it may re-allocate nodes,
> thus voiding any iterators.

This is not permitted for the standard C++ containers.

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

Yes, deque does work that way, and has iterator validity
rules fairly similar to vector (but you can add items at
either end of a deque without invalidating iterators).

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

All of C++'s standard node-based iterators preserve iterators
to existing items on deletions.

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

That's an oversimplification, I'm afraid.

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

It does match the behaviour of set though, so maybe you
need to check your assumptions.

-- James