Inserting in a set while traversing well-defined?

J

Johannes Bauer

Hello group,

I currnetly have the following problem: I traverse a std::set using
iterators. During the traversal, I insert elements in the set.

1. Are the results well-defined?
2. Am I guaranteed to see all elements contained in the set during my
traversal? If not, what container makes such a guarantee (vector I assume?)

Kind regards,
Johannes
 
J

Johannes Bauer

Johannes said:
1. Are the results well-defined?

Just now I saw: "Set has the important property that inserting a new
element into a set does not invalidate iterators that point to existing
elements."

So this question is answered: Yes, they are.
2. Am I guaranteed to see all elements contained in the set during my
traversal? If not, what container makes such a guarantee (vector I assume?)

This question, however, is still open...

Kind regards,
Johannes
 
J

Johannes Bauer

Pete said:
It just takes a little thought: Where in the set will the new element go?

Indeterministic. Depends on the element, the search order and the
elements currently in the set.

However, this does not mean the iterator could be cleverly designed to
also catch those elements which got in later. Thus my question.

Kind regards,
Johannes
 
K

Kai-Uwe Bux

Johannes said:
Just now I saw: "Set has the important property that inserting a new
element into a set does not invalidate iterators that point to existing
elements."

So this question is answered: Yes, they are.


This question, however, is still open...

The answer is no, unless the element you insert always ends up after the
element you are looking at. Traversal order of iterators into a set agrees
with the order of the set given by the comparison predicate (std::less by
default).

As for which container makes that guarantee: none. However, you could use
std::list and always insert at the end. The two other sequence containers
(vector and deque) suffer from iterator invalidation upon insertion.


Best

Kai-Uwe Bux
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top