CODEWITHSUNDEEP
c++stliterator
jerron
jerron

Reputation: 343

insert elements while iterating a sorted stl container

I found unexpected result while my code insert element into std::set while iterating it. I need enlightenment on it.

Here is the test code:

    template<class Ti, class T>
    void iteration_insertion(Ti start, Ti end, T& S){
        for (auto ite=start;ite!=end;++ite){
            auto before=*ite;
            if(*ite % 2)
                S.insert(*ite*2);
            else
                S.insert(*ite/2);
            if(before!=*ite)
                cout<<before<<","<<*ite<<endl;
        }
    }
    void test() {
        set<int> S1({4,7,10,13}),S2(S1);
        cout<<"ascending\n";
        iteration_insertion(S1.begin(),S1.end(),S1);
        cout<<"descending\n";
        iteration_insertion(S2.rbegin(),S2.rend(),S2);
    }

and the result:

ascending
descending
13,26

As we can see the element where iterator points to is changed after insertion, sometimes. But I can't tell when it would happen. In the test code it only happened once, for 13 in descending. Why there is no such mismatch in the ascending iteration? Why there is no mismatch for 7 in descending iteration? How to prevent it from happening? I'm fine with the new added value could be iterated later, which is expected. I just don't want the iterator changed by insertion.

The test code can be a generic heuristic practice: from each current state generating new states for further check.

Upvotes: 1

Views: 266

Answers (2)

Qaz
Qaz

Reputation: 61970

In order to account for all elements of the container, a reverse iterator stores the iterator for the element past the one you get when you dereference it. For example, the result of rbegin() internally stores a one-past-the-end iterator. When you dereference, a copy of the stored iterator is made and that copy is decremented before it is dereferenced.

Essentially, a simplified version of the standard code used:

template<typename Iter>
struct reverse_iterator {
    Iter base;

    auto& operator++() { --base; return *this; }
    auto& operator*() {
        auto copy = base;
        --copy;
        return *copy;
    }
};

auto std::set::rbegin() {
    return reverse_iterator{this->end()};
}

Applying this to your situation, you start with rbegin(). Dereferencing this gives you the last element, 13. When you insert 26, it is inserted after 13, but before the one-past-the-end iterator that is stored internally within ite. When you dereference ite again, a copy of the internal one-past-the-end iterator is made and that is decremented to the position between 13 and 26, then dereferenced to give 26.

Here is the picture version of the explanation in case that helps:

diagram showing ite's internal iterator

Upvotes: 3

Sam Varshavchik
Sam Varshavchik

Reputation: 118435

A std::set

contains a sorted set

of values. Emphasis on the "sorted" part. Inserting a new value into the set does not invalidate any existing iterator, so inserting is valid, on its own merits.

However, because the container always contains a "sorted" set, if the newly inserted value is greater than the one your iterator is referencing, and you advance the iterator forward, at some point you will iterate over the new value, because it is now a part of the set, which must always be in sorted order.

If the new value is less than your iterator's currently referenced value, advancing the iterator forward will not iterate over the new value, by definition.

There is no way to "prevent it from happening" because this is how std::sets work, by definition. You will need to "prevent it from happening" all by yourself. Perhaps by inserting any new values into a separate std::vector, and after you're done iterating you then insert the accumulated new values, from that vector, into your set.

Upvotes: 0

Related Questions