вставлять элементы во время итерации отсортированного контейнера stl

Question

Я обнаружил неожиданный результат, когда мой код вставлял элемент в std :: set во время его итерации.Мне нужно просветление.

Вот код теста:

    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);
    }

и результат:

ascending
descending
13,26

Как мы видим элемент, на который указывает итераторменяется после вставки, иногда.Но я не могу сказать, когда это произойдет.В тестовом коде это произошло только один раз, за ​​13 по убыванию.Почему в восходящей итерации такого несоответствия нет?Почему нет несоответствия для 7 в нисходящей итерации?Как предотвратить это?Я в порядке с новой добавленной стоимостью, может быть повторен позже, что ожидается.Я просто не хочу, чтобы итератор изменялся путем вставки.

Тестовый код может быть общей эвристической практикой: из каждого текущего состояния генерируются новые состояния для дальнейшей проверки.

Answer 1

Чтобы учесть все элементы контейнера, обратный итератор сохраняет итератор для элемента после того, который вы получили при разыменовании. Например, результат rbegin() внутренне хранит итератор «один за другим». При разыменовании создается копия сохраненного итератора, и эта копия уменьшается до того, как на нее разыменовывается.

По сути, используется упрощенная версия стандартного кода:

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()};
}

Применяя это к вашей ситуации, вы начинаете с rbegin(). Разыменование дает вам последний элемент, 13. Когда вы вставляете 26, он вставляется после 13, но до итератора «один за другим», который хранится внутри ite. Когда вы снова разыменовываете ite, создается копия внутреннего итератора «один за другим», который уменьшается до положения между 13 и 26, а затем разыменовывается, чтобы получить 26.

Вот вариант пояснения к рисунку, который помогает:

Answer 2

A std :: set

содержит отсортированный набор

значений.Акцент на «отсортированную» часть.Вставка нового значения в набор не делает недействительным ни один из существующих итераторов , поэтому вставка действительна по своим достоинствам.

Однако, поскольку контейнер всегда содержит «отсортированный» набор, если вновь вставленное значение больше того, на которое ссылается ваш итератор, и вы продвигаете итератор вперед, в какой-то момент вы будете перебирать новое значение, потому что оно теперь является частьюиз набора, который всегда должен быть в отсортированном порядке.

Если новое значение меньше текущего значения, на которое ссылается ваш итератор, продвижение вперед итератора не будет перебирать новое значение по определению.

Нет способа «предотвратить это», потому что так работает std::set по определению.Вам нужно будет «предотвратить это» самостоятельно.Возможно, вставив какие-либо новые значения в отдельный std::vector, и после того, как вы закончите итерацию, вы вставите накопленные новые значения из этого вектора в ваш набор.